프로그래머스 Lv2 소수찾기 Kotlin

문제

• https://programmers.co.kr/learn/courses/30/lessons/42839

풀이방법

• 현재 주어진 String으로 만들 수 있는 가장 큰 값을 max로 두고 에라토스테네스의 체 적용, 소수를 먼저 구한다.

• 재귀로 조합을 만들어 각 수가 소수인지 확인하고 011 = 11처럼 같은 값을 조합할 것을 대비해 HashSet에 기존에 소수라고 판별했던 수들을 저장하여 이때는 카운트 하지 않도록 구현하였다.

코드

class Solution {
    lateinit var isPrime : BooleanArray
    lateinit var visit : BooleanArray
    var sb = StringBuilder()
    var cnt = 0
    var primeSet = HashSet<Int>()
    fun solution(numbers: String): Int {
        var maxNum = numbers.toCharArray().sortedDescending()
        var max= ""
        maxNum.forEach{
            max += it
        }
        isPrime = BooleanArray(max.toInt()+1){true}
        visit = BooleanArray(numbers.length){false}
        isPrime[0] = false
        isPrime[1] = false
        isPrime[2] = true
        for(i in 2..max.toInt()){
            if(!isPrime[i]) continue
            var j = i*2
            while(j<=max.toInt()){
                isPrime[j] = false
                j += i
            }
        }
        dfs(0,numbers)
        return cnt
    }
    fun dfs(depth : Int, numbers: String){
        if(sb.length!=0){
            if(isPrime[sb.toString().toInt()]&&!primeSet.contains(sb.toString().toInt())){
                cnt++
                primeSet.add(sb.toString().toInt())
            }
        }
        if(depth==numbers.length){
            return
        }
        for(i in 0 until numbers.length){
            if(!visit[i]){
                sb.append(numbers[i])
                visit[i] = true
                dfs(depth+1,numbers)
                visit[i] = false
                sb.deleteCharAt(depth)
            }
        }
    }

}