[ JavaScript ] 프로그래머스 level2 42839번 소수찾기

소수찾기 #42839

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

문제 설명

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

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

제한사항

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

입출력 예numbersreturn

"17"	3
"011"	2

입출력 예 설명

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

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

• 11과 011은 같은 숫자로 취급합니다.

나의 풀이

function solution(answers) {
  const nums = answers.split("").sort((a, b) => b - a); // 내림차순 정렬
  const max = parseInt(nums.join("")); // 만들어질 수 있는 가장 큰 수
  let count = 0;

  for (let i = parseInt(nums[nums.length - 1]); i <= max; i++) {
    // 최솟값부터 최댓값까지 1씩 증가시킴
    const tempNums = nums.map((n) => n); // 기존 nums 배열을 임시 저장하는 배열

    const available = `${i}`.split("").every((num) => {
      const idx = tempNums.indexOf(num);
      if (idx !== -1) tempNums.splice(idx, 1);
      // 해당 숫자가 nums에 존재하면 index 반환, 없으면 -1 반환
      // 존재하면 tempNums배열의 해당 인덱스의 숫자를 제거함 (splic)
      return idx !== -1;
      // 존재여부를 반환 => 최종적으로, 모든 숫자가 존재하는지를 확인(every)
    });

    if (available && isPrime(i)) count++; // 만들어질 수 있는 숫자면서 소수면 count를 증가
  }

  return count;
}

/* 소수인지 판별하는 함수 */
const isPrime = (num) => {
  if (num <= 1) return false; // 1과 0은 소수가 아님
  if (num === 2) return true; // 2는 소수

  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (num % i === 0) return false;
  }
  return true;
};

• 만들어질 수 있는 숫자들 경우의 수를 모두 찾아야해서 어렵게 느껴졌다. 
• 풀면서도 이건 아닐 거 같은데 싶었지만, 다른 방법이 도저히 떠오르지 않아 일단 이렇게라도 풀어버렸다. 
  
  
• numbers를 내림차순으로 정렬하고, join 하면 만들어질 수 있는 가장 큰 수이고, 이 값을 max에 저장한다. 
• numbers를 내림차순 정렬했으므로, 가장 마지막 요소는 만들어질 수 있는 가장 작은 수 이다. 
• 이 수부터 max까지 1씩 증가시키면서, 이 수가 주어진 카드들로 만들어질 수 있는 숫자인지 판단하고, 소수인지 판별하여 count를 증가시킨다. 
  
  
• 어찌저찌 풀긴했으나, 이 방법은 최악이라고 생각이들며, 역시나 소요시간도 매우 오래 걸리는 코드이다. 

 

다른풀이 (재귀)

function solution(numbers) {
  let answer = 0;

  const n = numbers.split("");
  const nums = new Set(); // 중복되지 않는 숫자 조합을 저장하기 위해 Set 사용

  const combi = (a, s) => {
    // a: 현재 조합을 만들기 위해 사용할 수 있는 숫자 배열, s: 현재까지 생성된 숫자 조합 문자열

    if (s.length > 0) {
      if (nums.has(Number(s)) === false) {
        nums.add(Number(s));
        if (isPrime(Number(s))) answer++;
      }
    }
    if (a.length > 0) {
      for (let i = 0; i < a.length; i++) {
        let t = a.slice(0); // 배열의 얕은 복사본을 만듦
        t.splice(i, 1);
        combi(t, s + a[i]);
      }
    }
  };

  combi(n, ""); // 재귀함수 combi 호출
  return answer;
}

• 중복되지 않는 숫자 조합을 저장하기 위해 Set을 사용 (nums)
• 재귀함수로 사용할 combi의 로직은 아래와 같다.
  • 파라미터로
    • a : 현재 조합을 만들기 위해 사용할 수 있는 숫자 배열 ( 최초값 : n = 모든 숫자 배열 )
    • s : 현재까지 생성된 숫자 조합 문자열 ( 최초값 : "" ) 
  • s의 길이가 0보다 크면 
    • nums Set에 해당 숫자 조합 문자열이 있는지 확인 후,
    • 있으면, nums에 추가하고, 
    • 해당 숫자가 소수이면 answer 를 1증가시킴
  • a의 길이가 0보다 크면 
    • a의 길이만큼 for문을 돌린다. 
      • a의 복사본인 t를 생성 (slice(0) 은 배열의 얕은 복사본을 생성함) 
      • t를 하나씩 잘라서, (splice)  => 잘라낸 문자의 인덱스가 i 
      • combi 재귀함수를 호출하는데, 파라미터로 현재 t와, s에 잘라낸 문자열을 더해서 넘겨준다. 
• answer를 리턴한다. 
• 소수인지 판별하는 함수는 나의 풀이와 동일

 

나의 풀이와 재귀 사용한 다른 풀이의 비교

 

포인트

• 재귀함수로 풀 생각 자체를 하기가 어려운데, 재귀함수로 풀 방법을 떠올리는 습관을 길러야겠다. 
• 배열의 복사본을 만들기 위해 map을 사용했었는데, slice(0)을 하면 배열의 복사본을 만들 수 있다. 
  • slice의 startIdx가 0이므로, 결국 전체를 복사하는 것
• "중복"과 관련되어 있으면 Set을 떠올릴 것