이런 재귀를 떠올릴 줄 알 때까지 열심히 하자 !
소수 찾기
문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.
해결한 코드
function solution(numbers){
var numberList = numbers.split('')
var answers = findPrimeNumbers(numberList)
return [...new Set(answers)].length
}
function primeNumber(numbers){
var nonPrime = [0,1]
if(nonPrime.includes(numbers)) return false
for(var i=2; i*i<=numbers; i++){
if(number % i === 0) return false
}
return true
}
function findPrimeNumber(numberList, preNumber){
var frontNumber = preNumber || ''
return numberList.reduce((primeNumbers, number, index) =>{
if(primeNumber(Number(frontNumber+number)){
primeNumbers.push(Number(frontNumber+number))
}
var nextNumberList = [...numberList]
nextNumberList.splice(index, 1)
var result = findPrimeNumber(nextNumberList, frontNumber+number)
primeNumbers.push(...result)
return primeNumbers
}, [])
}
알고리즘
- numbers를 쪼개 배열 numberList에 담는다.
1-1. numberList = ['1', '7']- 배열을 돌면서 만들 수 있는 수(1, 17, 7, 71)를 만들며 소수인지 아닌지 판별한다.
사실 2번에서 재귀로 돌리며 풀어나가는 과정을 이해하기 어려웠다. 이를 차근히 풀어 써보고자 한다.
2-1. ( '1'을 reduce 할 때 ) frontNumber = '', primeNumbers = [ ]로 초기화
2-2. Number(frontNumber+'1') = 1 이 소수인지 아닌지 판별
2-3. 소수가 아니기 때문에 primeNumbers = [ ]
2-4. nextNumberList = ['1', '7']
2-5. 현재 index == 0, 따라서 splice(0, 1) -> nextNumberList = [ '7' ]
2-6. result = findPrimeNumber( [ '7' ], '1' )
2-7. ( result 구하는 중 ) Number('1' + '7') = 17 은 소수이므로, primeNumbers = [ 17 ]
2-8. ( result 구하는 중 ) nextNumberList = [ '7' ]
2-9. ( result 구하는 중 ) splice -> nextNumberList = [ ]
2-10. ( result 구하는 중 ) findPrimeNumber([ ], '1' + '7')
2-11. ( result 구하는 중 ) result = findPrimeNumber([ ], 17 ) <- result 계산 불가능. 재귀 종료.
2-12. ( result 구하는 중 ) primeNumbers = [ 17, ]
2-13. 이를 return --> ( result 구함 ) result = [ 17 ]
2-14. primeNumbers에 result 원소를 넣음
2-15. 이를 return --> primeNumbers = [ 17 ]
2-16. ( '7' 을 reduce 할 때 ) frontNumber = '', primeNumbers = [ ]로 초기화
2-17. Number(frontNumber+'7') = 7 이 소수인지 아닌지 판별
2-18. 소수이기 때문에 primeNumbers = [ 7 ]
2-19. nextNumberList = ['1', '7']
2-20. 현재 index == 1, 따라서 splice(1, 1) -> nextNumberList = [ '1' ]
2-21. result = findPrimeNumber([ '1' ], '7' )
2-22. ( result 구하는 중 ) Number( '7' , '1' ) = 71은 소수이므로, primeNumbers = [ 71 ]
2-23. ( result 구하는 중 ) splice -> NextNumberList = [ ]
2-24. ( result 구하는 중 ) result = findPrimeNumber([ ], '7'+'1') <- result 계산 불가능. 재귀 종료
2-25. ( result 구하는 중 ) primeNumbers = [ 71 ]
2-26. 이를 return --> ( result 구함 ) result = [ 71 ]
2-27. primeNumbers에 result 원소를 넣음
2-28. 이를 return --> primeNumbers = [ 7, 71 ]
2-29. 최종 primeNumbers = [ 17, 7, 71]
이렇게 담긴 primeNumbers 배열을 solution에서 중복값을 제거하고 그 길이를 반환하면 끝.
- Set을 사용하여 중복값을 제거한다. length를 구한다.
내가 생각했던 방식은 다음과 같다.
나의 알고리즘
- numbers로 만들 수 있는 최댓값을 구한다.
1-1. numbers = "17" 이라면, 71이 최댓값- 2~71까지의 소수를 모두 구한다. 이를 num_array에 담는다.
- (위에서 한 재귀같이) 1, 17, 7, 71 순서로 돌며 해당 수가 num_array에 includes인지 아닌지 확인한다.
- includes이면 이를 primeNumbers에 담는다.
- primeNumbers의 길이를 구하면 끝.
하지만 이 방법은 시간초과에 걸리는 문제가 생겼다. 소수를 모두 구해서 시간이 많이 걸린 것 같다.
소수 찾기와 같은 찐 수학(?) 문제같은 것들.. 내겐 너무 어렵다 ㅠㅠ 게다가 이렇게 재귀를 잘 활용할 줄 아는 사람의 코드를 보아하니... 안 그래도 멀게만 느껴지던 갈 길이 더더욱 멀어진 것 같은 느낌이 든다.
그래도 가지 않으면 그 목적지에 가까워 질 수 없다 ! 조금씩이라도 포기하지 말고 꾸준히 가자 !
