[Programmers] 소수찾기 - kotlin

소수찾기 (Level2)

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

코딩테스트 연습 - 소수 찾기

 

1. 문제 파악하기

- 입력 : 숫자로 구성된 문자열 (ex. 17)

- 출력 :문자열에 포함된 숫자들로 구성할수있는 숫자들중에서 소수의 개수를 찾는다 

 

2. 아이디어

- 먼저 소수인지 판단할수있는 함수 isP를 생성한다 (소수이면 true / 아니면 false 반환)

- 이제 문자열 속 숫자들로 만들수 있는 조합을 모두 만들어 소수인지 확인한다 

- dfs를 돌며 모든 조합을 만든다. 모든 조합이기 때문에 순서 까지 고려해야한다 단순히 뽑기만 하는것이라면 순서 상관없이 같은것을 뽑는 경우만 체크하면 되겠지만 순서를 고려해야 하기 때문에 같은 숫자를 사용하더라도 다른 순서의 조합이면 서로다른 경우로 생각하다 

ex) 12345의 숫자들중 '1''2''3'을 단순히 뽑는 경우는 '1''2''3' / '2''3''1' 이가 같은 경우겠지만 순서가 고려되어야 하기때문에 두 조합은 다른것으로 판단

-  대신 숫자가 중복으로 사용되는것은 안되기대문에 visit 배열을 생성하여 중복 사용을 방지한다 

 

3. 풀이

class Solution {
    var answer = 0
    var number = ""
    var visit = Array<Boolean>(0) {false}
    var answerSet: MutableSet<Int> = mutableSetOf()
    fun solution(numbers: String): Int {
        number = numbers
        visit = Array<Boolean>(numbers.length) {false}
        
        for(i in 0 until numbers.length) {
            visit[i] = true
            dfs(numbers[i].toString().toInt())
            visit[i] = false
        }
        return answerSet.size
    }
    fun dfs(num: Int) {
        if(isP(num)) {
            answerSet.add(num)
        }
        
        for (i in 0 until number.length) {
            if (!visit[i]) {
                var t = num.toString() + number[i].toString()
                visit[i] = true
                dfs(t.toInt())
                visit[i] = false
            }
        }
    }
    
    fun isP(num: Int): Boolean {
        if (num == 1 || num == 0) return false 
        for(i in 2 .. num/2) {
            if (num % i == 0) {
                return false    
            }
        }
        return true
    }
}