문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 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 isPrime(num) {
if (num <= 1) return false;
if (num === 2) return true;
for (var i = 2; i <= Math.sqrt(num); i++) {
if (num%i === 0) return false;
}
return true;
}
function solution(numbers) {
var num_array = numbers.split(''); // 배열화
var primeNums = [];
function solution2(first, second) {
if (second.length > 0) { // 두 번째 인자에서는 숫자가 소수인지 판단
if (primeNums.indexOf(Number(second)) === -1) { // nums 안에 이 숫자가 들어있지 않으면,
if (isPrime(Number(second))) {
primeNums.push(Number(second));
}
}
}
if (first.length > 0) { // 첫 번째 인자에서는 배열을 쪼개서 모든 숫자를 비교할 수 있도록 함.
for (let i = 0; i < first.length; i++) {
let t = first.slice(0);
t.splice(i, 1); // 반복문을 돌려서 first의 모든 값들을 뒤로 돌려준다.
solution2(t, second + first[i]);
}
}
}
solution2(num_array, ''); // 배열과 빈 문자열을 넣어줌.
return primeNums.length;
}
이 문제를 푸는 데는 꼬박 이틀이 걸렸다. 문제를 차근차근 읽고 먼저 어떻게 접근하는 것이 좋을지 생각해보았다.
이 문제는 다음과 같이 접근할 수 있다.
1. 주어진 숫자 문자열을 배열로 전환해준다.
2. 배열의 요소들을 조합하여 배열의 요소로 만들 수 있는 모든 숫자들을 만들어낸다.
3 이 숫자들이 소수인지 아닌지 판단한다.
4. 이 숫자들의 중복 여부를 체크하고 서로 다른 숫자들을 전부 primeNums 배열에 저장해둔다.
5. primeNums 배열의 길이를 결과값으로 반환한다.
주어진 숫자들에 대해 소수인지 아닌지 판단하는 함수는 이전에 짜본 적이 있어서 무리 없이 짤 수 있었다.
배열의 요소들을 조합하여 가능한 모든 숫자들을 만드는 과정에서 많이 헤맸다. 구글을 이용하여 검색을 해보던 도중 순열 알고리즘을 이용하면 해결할 수 있다는 것을 알게 되었다. 하지만 순열 알고리즘이 재귀 함수로 구성되어 있어서 코드를 이해하는 데 어려움이 많았다. 많은 자료를 보며 이해하였고 여러 시행착오 끝를 겪고 나서야 풀 수 있었다.
solution2 함수의 동작 순서
solution2 함수는 숫자 문자열들로 구성된 배열과 동적으로 바뀌는 문자열을 인자로 가진다.
먼저 배열 내 각각의 요소에 접근한다.
각 요소들을 첫 번째로 추출하여 이를 두 번째 인자에 더하며, 재귀적으로 solution2 함수를 호출한다.
두 번째 인자로 받은 문자열을 숫자로 변환하여 소수인지 여부를 판단한다. 소수라면 primeNum 배열에 추가한다.
이어서, 앞의 요소부터 순서대로 추출하며 두 번째 인자에 이를 이어붙이고 소수인지 여부를 판단한다.
이와 같은 과정이 배열의 요소가 존재하지 않을 때까지 재귀적으로 계속 반복된다.
이해를 돕기 위해, 예시를 살펴보자.
입력받은 문자열은 "011"이고, 이를 배열로 바꿔주면 ["0", "1", "1"]와 같은 형태를 가지고 있다.
이 배열을 solution2 함수의 첫 번째 인자로, 빈 문자열을 두 번째 인자로 넣고 호출해보자.
solution2(["0", "1", "1"], '') 호출
- i = 0일 때, solution2(["1", "1"], "0") 호출 => "0"은 0으로 변환되고 소수가 아니라고 판단 =>
solution2(["1", "1"], "0") 내의 for 문이 수행된다.
- i = 0일 때, solution2(["1"], "01") 호출 => "01"은 1로 변환되고 소수가 아니라고 판단 => solution2([ ], "011") 호 출 => "011"은 11로 변환되고 소수라고 판단되어 primeNums 배열에 저장된다. => i = 0 일 때의 모든 동작이 완료되어 i++ 로 넘어온다.
- i = 1일 때, solution2(["1", "01") 호출 => "01"은 1로 변환되고 소수가 아니라고 판단 => solution2([ ], "011") 호 출 => "011"은 11로 변환되고 소수라고 판단되지만 이미 primeNums 배열에 저장되어 있다.
=> i = 0 일 때의 모든 동작이 완료되어 i++ 로 넘어온다.
- i = 1일 때, solution2(["0", "1"], "1") 호출 => "1"은 1로 변환되고 소수가 아니라고 판단 => solution2(["1", "1"], "0") 내의 for 문이 수행된다.
- i = 0일 때, solution2(["1"], "10") 호출 => "10"은 10으로 변환되고 소수가 아니라고 판단 => solution2([ ], "101") 호출 => "101"은 101로 변환되고 소수라고 판단되어 primeNums 배열에 저장된다. => i = 0 일 때의 모든 동작이 완료되어 i++ 로 넘어온다.
- i = 1일 때, solution2(["0"], "11") 호출 => "11"은 11로 변환되고 소수라고 판단되어 primeNums 배열에 저장된 다. => solution2([ ], "110") 호출 => "110"은 110으로 변환되고 소수가 아니다.
=> i = 1 일 때의 모든 동작이 완료되어 i++ 로 넘어온다.
- i = 2일 때, solution2(["0", "1"], "1") 호출 => "1"은 1로 변환되고 소수가 아니라고 판단 => solution2(["0", "1"], "1") 내의 for 문이 수행된다.
- i = 0일 때, solution2(["1"], "10") 호출 => "10"은 10으로 변환되고 소수가 아니라고 판단 => solution2([ ], "101") 호출 => "101"은 101로 변환되고 소수라고 판단되지만 이미 primeNums 배열에 저장되어 있다. => i = 0 일 때의 모든 동작이 완료되어 i++ 로 넘어온다.
- i = 1일 때, solution2(["0"], "11") 호출 => "11"은 11로 변환되고 소수라고 판단되지만 이미 primeNums 배열에 저장되어 있다. => solution2([ ], "110") 호출 => "110"은 110으로 변환되고 소수가 아니라고 판단
=> 이로써 solution2 함수가 종료된다.
primeNums 배열에는 11, 101이 저장되어 있다.
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [스택/큐] 같은 숫자는 싫어 (0) | 2022.11.23 |
|---|---|
| [프로그래머스 - SQL] 상품 별 오프라인 매출 구하기 (0) | 2022.11.22 |
| [JS] 프로그래머스 - 위장 (0) | 2020.11.14 |
| [JS] 프로그래머스 - 괄호 변환(레벨2) (0) | 2020.11.09 |
| [JS] 프로그래머스 - 가장 큰 수(레벨 2) (0) | 2020.11.08 |