문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한사항
- numbers는 길이 1 이상 7 이하인 문자열입니다.
- numbers는 0~9까지 숫자만으로 이루어져 있습니다.
- "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
입출력 예
| numbers | return |
|---|---|
| "17" | 3 |
| "011" | 2 |
입출력 예 설명
예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.
- 11과 011은 같은 숫자로 취급합니다.
풀이
처음 문제를 봤을 때 이중 반복 또는 7회 반복으로 경우의 수를 계산하려 했다. 곰곰이 생각해봤을 때 반복문으로 돌리는 것보다 이진트리 탐색으로 하는 게 더 편할 거 같았다. 그래서 깊이 우선 탐색 방법을 이용해서 풀었다.
과정을 총 3가지이다.
- 소수 판별 함수
- 변수 선언
- 탐색에 쓰일 재귀 함수
1. 소수 판별 함수
소수의 정의 : 소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수
함수에 쓰일 조건은 2개로 볼 수 있다. 패러미터가 1 이상, 자기 자신을 제외한 수로 나누어 떨어지지 않을 경우
//소수 판별
fun checkSosu(number: String): Boolean{
var n = number.toInt()
if(n <= 1)
return false
for(i in 2 ..round(sqrt(n.toDouble())).toInt()){
if(n % i == 0)
return false
}
return true
}String타입의 number를 패러미터로 선언해준다. String타입으로 해준 이유는 문제에서 String타입으로 주고 있기 때문이다. number을 Int로 타입 캐스팅 해준 뒤 변수에 할당해준다.
일단 Int타입으로 캐스팅 한 이유는 입출력 예에서 11과 011은 같은 숫자로 취급합니다.라고 명시해줬기 때문이다. Int타입으로 캐스팅해주면 알아서 앞자리 0이 사라지기 때문에 편의상 변경했다.
그리고 효율을 위해서 반복문을 2에서 ⌈패러미터의 제곱근⌉까지 반복해줬고 나누어 떨어졌을 경우 소수가 아니므로 false를 리턴해준다.
2. 변수 선언
필요한 변수가 꽤 된다. companion object로 선언한 answer과 mergedNumbers, 문자열을 합치는데 필요한 StringBuilder(), 노드 방문 여부에 필요한 visited 총 4가지이다.
companion object{
var answer = 0
val mergedNumbers = ArrayList<Int>()
}answer은 정답을 저장할 변수이고 mergedNumbers는 중복을 방지하기 위해 만든 Int리스트이다. "111"이 패러미터로 넘어올 경우
중복 방지를 해주지 않으면 11, 11, 11 answer=3이 나올 수 있다.
val sb = StringBuilder()
val visited = BooleanArray(numbers.length)문자열을 숫자로 변경해서 쓸게 아니라 문자열 자체로 쓸 것이기 때문에 문자열 합치는데 용이한 StringBuilder객체를 사용한다. visited는 노드 방문 시 자기 자신을 반복하는 것으로 무한루프를 막기 위해 만들어 뒀다.
3. 탐색에 쓰일 재귀 함수
함수에 어떤 패러미터가 필요한 시 함수 시그니처를 살펴보자
fun doMerge(numbers: String, sb: StringBuilder, cnt: Int, visited: BooleanArray)반복에 필요한 numbers, 조합에 필요한 StringBuilder, 깊이 파악 용인 cnt, 방문 여부 visited
재귀 함수를 작성할 때 가장 먼저 해줘야 할 작업은 재귀를 끝내거나 피할 조건을 적는 것이다. 이 함수는 조건이 3가지다.
- 소수가 아닐 시
- 중복일 시
- 리프 노드에 도달 시
코드로 적어주면 아래와 같다.
if(checkSosu(sb.toString()) && !mergedNumbers.contains(sb.toString().toInt())){ //<- toInt 마지막에 추가한거
mergedNumbers.add(sb.toString().toInt())
answer++
}
if(cnt == numbers.length)
return1번과 2번은 피해야 할 조건, 3번은 종료 조건이다. 첫 번째 if문에서 소수이면서 중복이 아니면 중복 리스트에 추가하고 정답에 1을 더해준다.
for (i in numbers.indices){
if(!visited[i]) {
visited[i] = true
sb.append(numbers[i])
val s = sb.lastIndex
doMerge(numbers, sb, cnt+1, visited)
visited[i] = false
sb.deleteAt(s)
}
}반복문을 문자열의 길이만큼 돌린다. 각 문자를 방문하지 않았을 때 StringBuilder()에 추가 후 재귀 호출한다. 호출이 종료되면 방문 여부를 false로 바꿔주고, StringBuilder()를 원상복구 해준다.
fun solution(numbers: String): Int {
for(i in numbers.indices){
val sb = StringBuilder()
val visited = BooleanArray(numbers.length)
sb.append(numbers[i])
visited[i] = true
doMerge(numbers, sb, 1, visited)
}
return answer
}처음 호출은 루트 노드에서 시작하므로 동일한 과정을 만들어주되 sb를 원상복구 할 필요는 없다.
전체 코드
class Solution {
companion object{
var answer = 0
val mergedNumbers = ArrayList<Int>()
}
fun solution(numbers: String): Int {
for(i in numbers.indices){
val sb = StringBuilder()
val visited = BooleanArray(numbers.length)
sb.append(numbers[i])
visited[i] = true
doMerge(numbers, sb, 1, visited)
visited[i] = false
}
return answer
}
//경우의 수
fun doMerge(numbers: String, sb: StringBuilder, cnt: Int, visited: BooleanArray){
if(checkSosu(sb.toString()) && !mergedNumbers.contains(sb.toString().toInt())){ //<- toInt 마지막에 추가한거
mergedNumbers.add(sb.toString().toInt())
answer++
}
if(cnt == numbers.length)
return
for (i in numbers.indices){
if(!visited[i]) {
visited[i] = true
sb.append(numbers[i])
val s = sb.lastIndex
doMerge(numbers, sb, cnt+1, visited)
visited[i] = false //<- 마지막에 추가한 거
sb.deleteAt(s)
}
}
}
//소수 판별
fun checkSosu(number: String): Boolean{
var n = number.toInt()
if(n <= 1)
return false
for(i in 2 ..round(sqrt(n.toDouble())).toInt()){
if(n % i == 0)
return false
}
return true
}
}