프로그래머스 소수찾기 2단계 코틀린 완전탐색

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

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

안녕하세요! 

추석 당일 오늘 아침에 소수찾기 문제를 풀었습니다!

사실 이 문제는 엄청 예전부터 풀고 있었던 문제인대 

몇일동안 고민하고 다른 분들 블로그를 참고 하면서 까지 공부해서 풀려고 했는대도 게속 못 풀었는대

결국 풀었습니다 후... 힘드네요...

 

문제 설명

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

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

제한사항

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

입출력 예

 

numbers	return
"17"	3
"011"	2

---

제가 생각한 풀이 방법은 

 

재귀함수를 이용해서 문자열 하나씩 기준으로 다른 문자 하나씩 붙어서 소수인지 확인합니다 이때 중요한 점은 재귀함수의 depth를 문자열 길이만큼 호출 하고 문자열 길이가 depth 와 같으면 해당 문자열이 소수인지 체크 후 리턴 합니다! 

 

저도 100프로 이해한 상태가 아니라서 제 설명이 너무 부실하네요 ㅠㅠ 죄송합니다...

더 고민하고 공부해서 나중에 설명 보충하겠습니다...ㅠㅠㅠㅠ

 

class Solution {
    var numbers :String=""
    lateinit var check : BooleanArray
    var answerSet = mutableSetOf<Int>()
    fun solution(numbers: String): Int {
        this.numbers = numbers
        check = BooleanArray(numbers.length)
        search(0,"")
        return answerSet.size
    }
    fun search(depth : Int , str : String){

        if(depth==numbers.length){
            if(str!=""){
                if(checkPrime(str.toInt())){
                    answerSet.add(str.toInt())
                }
            }else return
            return
        }

        for(i in numbers.indices){
            if(!check[i]){
                check[i] = true
                search(depth+1, str+numbers[i])
                check[i] = false
                search(depth+1,str)
            }
        }


    }
}

fun checkPrime(number : Int) : Boolean{
    var isPrime = true
    for(i in 2 until number){
        if(number % i ==0){
            isPrime = false
            break
        }
    }
    if(number<=1) return false
    return isPrime
}