[JavaScript] 프로그래머스 코딩테스트 레벨 2 : 소수 찾기

📌  문제

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

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

📌  제한사항

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

📌  입출력 예

numbers	return
"17"	3
"011"	2

---

📌  풀이

알아야 하는 것

• 소수 구하는 공식

소수는 1과 자기 자신으로만 나눠지는 수를 말한다. 주어진 자연수가 2보다 작다면 1이 되는데, 1은 소수가 아니라 1차 탈락 조건이다. 소수나 약수를 구할 때 주어진 수만큼 전개하는 것보다, 거듭제곱이나 제곱근을 사용하는 것이 효율적이다. 이 때 자기 자신이 아닌 다른 수로 나누어 떨어지는 경우 2차 탈락 조건으로 간주되며 1차 탈락 조건과 2차 탈락 조건에 모두 해당되지 않는 경우만 소수로서 true를 출력한다.

function isPrime(n) {
    if (n < 2) return false;
    for (let i = 2; i*i <= n; i++) { // 또는 i <= Math.sqrt(n)
        if (n % i === 0) return false
    }
    return true
}

구할 것

• solution 함수 (전체적인 해결 함수)
  • 문자열 numbers -> 배열 nums로 변경
  • 중복된 값을 걸러주기 위한 Set 생성
• dfs 함수 (dfs 전개를 위한 함수)
  • set, nums, ""을 파라미터로 전달 (""으로 초기값을 세팅해야 1번째 수부터 조합을 만들 수 있다.)
  • 종료 조건: nums.length >= 1 (전개하면서 splice로 잘라낸 부분을 새로운 nums로 전달할 것 === 길이가 1씩 감소)
  • 초기값 + nums[i]로 새로운 문자열 newStr 생성, 현재 nums에서 splice로 nums[i]를 잘라낸 배열을 새로운 newNums 생성
  • newStr이 현재 문자열이기 때문에 Number로 전환 (ex. "011" -> "11") 후 set에 add
  • dfs(set, newNums, newStr)로 재귀호출
• isPrime 함수 (소수 판단 함수)

 

솔루션 함수까지 포함해 총 3개의 함수를 사용했다.

예컨대 "17"이 주어질 경우, 1, 7, 17, 7, 1, 71로 6가지가 만들어지지만 중복을 제외하면 1, 7, 17, 71로 4가지다. 이 때 소수는 7과 17, 71이 해당되어 return 3이 되어야 한다. 

 

문자열을 배열로 변경하면 ["1", "7"]이 되어 있다. 이 때 1부터 전개해서 1, 7, 17, 7, 1, 71 을 만들려고 한다. dfs의 초기 세팅을 보면 (set, ["1", "7"], "")로 시작한다. 길이가 2이기 때문에 for문을 전개하는데, 하나씩 값을 붙이고 떼어내면서 값을 조합할 것이다.  

 

i = 0일 때 newStr = "" + nums[i] 로 "" + "1" 는 1이 된다. newNums = [...nums] = ["1", "7"]이지만 splice로 i번째 인덱스 1개를 잘라낸다. 즉 newNums = ["7"]이 된다. newStr = "1"을 숫자로 변경하면 1이 되는데, isPrime에 1을 인수로 전달하면 n < 2 에 해당되어 소수 판정을 받지 못한다. 따라서 set에 add 되지 않고 if문을 넘어가면서 dfs(set, ["7"], "1")로 재귀호출을 하게 된다.

 

1 -> 7 을 기점으로 시작하고 끝나면 i = 1 로 넘어가 7 -> 1 이 되는데 splice로 i번째 인덱스를 잘라내기 때문에 7을 잘라내서 7 + 1 로 또 전개되고 전개되고... splice로 해당되는 부분을 자르기 때문에 계속 자르고 붙일 수 있고, 이렇게 nums.length가 1보다 작아지면 재귀를 종료하게 된다.

 

function isPrime(n) {
    if (n < 2) return false;
    for (let i = 2; i*i <= n; i++) {
        if (n % i === 0) return false
    }
    return true
}

function dfs(set, nums, str) {
    if (nums.length >= 1) {
        for (let i = 0; i < nums.length; i++) {
            let newStr = str + nums[i];
            let newNums = [...nums];
            newNums.splice(i, 1);
            
            if (isPrime(Number(newStr))) {
                set.add(Number(newStr));
            }
            
            dfs(set, newNums, newStr)
        }
    }
}

function solution(numbers) {
    let nums = numbers.split("")
    let set = new Set();
    dfs(set, nums, "")
    
    return set.size;
}

 

"011"의 경우 0>1>1, 0>1>1, 1>1>0, 1>0>1, 1>0>1, 1>1>0 6번 전개된다.

0, 1, 10, 11, 101, 110 중에 소수는 11, 101만 남아서 2가 된다.

 

splice가 핵심이고 isPrime로 소수를 판별하는 조건을 효율화 시켜주지 않으니 시간 초과가 났다.

저번엔 약수 구하는 조건으로 썼는데 소수에서는 조건 하나만 추가하면 되니 이 부분을 숙지하자!