[Lv. 2] 소수 찾기

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

난이도 : Level.2

언어 : Kotlin

 

문제 설명 :

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

 

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

제한 사항 : 

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예 :

numbers	result
"17"	3
"011"	2

풀이 : 

import kotlin.math.sqrt

var primeList = mutableListOf<Int>()

class Solution {
    fun solution(numbers: String): Int {
        val numList = numbers.chunked(1).map { it.toInt() }.toIntArray()
        permutation(0, 0, BooleanArray(numList.size), numList, mutableListOf())

        return primeList.distinct().count()
    }

    fun permutation(cur: Int, cnt: Int, visited: BooleanArray, arr: IntArray, list: MutableList<Int>) {
        if (cnt <= arr.size) {
            val temp = list.joinToString("")
            if (temp.isNotEmpty() && isPrime(temp.toInt())) primeList.add(temp.toInt())
        }

        for (i in arr.indices) {
            if (visited[i]) continue

            visited[i] = true
            list.add(arr[i])
            permutation(cur, cnt + 1, visited, arr, list)
            list.removeAt(list.lastIndex)
            visited[i] = false
        }
    }

    fun isPrime(n: Int): Boolean {
        if (n <= 1) return false
        return (2 .. sqrt(n.toDouble()).toInt()).none { n % it == 0 }
    }
}