[프로그래머스/Kotlin] Lv2 소수찾기 : 완전탐색

문제 설명

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

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

제한사항

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

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

문제 풀이 아이디어

dfs로 푼 풀이도 있지만 나의 경우 완전탐색.. 그 자체로 풀었음을 미리 알린다.

예제로 0,1,1이 주어진다면 0,1,1 로 만들 수 있는 최대의 수를 구한다. ex) 110
그 다음 1부터 110 까지 반복문을 돌면서 이 사이에 소수인 수를 구한 뒤, 이 수의 각 자릿수가 0,1,1을 포함하고 있는지를 확인한다.

ex) 입력이 17일 경우 최대는 71, 1~71까지 돌면서 소수가 될 수 있는 값은 2,3,5,7, ... 71 이 중 7,17,71은 1과 7을 포함하는 수이므로 count를 ++ 한다.

코드

import java.lang.Math.*

class Solution {
    fun solution(numbers: String): Int {
        var numberList: MutableList<Int> = mutableListOf()
        numbers.forEach {
            numberList.add(it.toString().toInt())
        } // 예제 string의 각 값을 numberList에 담기

        numberList.sortByDescending {
            it
        } // numberList를 내림차순으로 정렬

        var number = ""
        numberList.forEach {
            number += it.toString()
        } // 내림차순한 numberList를 통해 최댓값 구함 구한 최댓값은 변수 number에 저장 
        
        var answer = 0
        for (i in 1..number.toInt()) { // 1.. number 까지 반복 
            if (isPrime(i)) {
                var numString = i.toString()
                var numListCopy = numberList.toMutableList()
                var idx = 0
                for (j in numString.indices) { // 한 숫자를 돌면서 numberList에 값이 있는지 확인 
                    for (k in numListCopy.indices) {
                        if (numString[j].toString().toInt() == numListCopy[k]) {
                            numListCopy[k] = -1 // 예제로 1,7 일 때 11 이면 이미 1이 사용되었음에도 같다고 볼 수 있기 때문에 중복 제거를 위한 처리 
                            idx++
                            break
                        }
                    }
                }
                if (idx == numString.length) { // 2자리 수 중에 numberList에 2자리 다 있으면 만들 수 있는 값이라 생각
                    answer++ // count를 올려준다.
                }
            }

        }
        return answer
    }

    fun isPrime(number: Int): Boolean { // 소수를 구하는 에라토스테네스의 체 함수 
        if (number == 0 || number == 1) return false
            for (i in 2..sqrt(number.toDouble()).toInt()) {
                if (number % i == 0) return false
            }
        return true
    }
}

배운점

현재 dfs 지식이 부족해서 정말 완전 탐색으로 풀었는데  좀 더 효율적인 방법으로 풀 수 있는 문제인거같다.

- 순열을 이용해서 풀 수 있음을 알게되었다. Kotlin의 순열에 대해서 알 수 있었는데, 파이썬처럼 순열 라이브러리가 따로 없어서 구현을 직접해야한다. 

- 소수 판별을 for문을 2부터 number까지 돌리면서 풀었는데, 이를 1부터 최대 number까지 반복하다보니 시간초과가 발생하였다. 이렇게 소수 판별하는 함수 말고 에스라토스테네스 체 소수 판별 알고리즘에 대해서 알게되었다. 

 fun isPrime(number: Int): Boolean {
        if (number == 0 || number == 1) return false
            for (i in 2..sqrt(number.toDouble()).toInt()) {
                if (number % i == 0) return false
            }
        return true
    }