[프로그래머스] Level 2 - 소수 찾기 (JavaScript)

구미·2021년 8월 26일

알고리즘

목록 보기

23/25

split까지 써두고 손놓고 있다가 다른 분들 풀이 보며 풀었다. 갈 길이 멀다 멀어 ... 🥲

🔍 제출한 코드

// 소수 판별 함수
function isPrime(num) {
  if (num < 2) return false;
  if (num === 2) return true;
  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (num % i === 0) return false;
  }
  return true;
}

// 만들 수 있는 소수가 몇 개인지 구하는 함수
function solution(numbers) {
  const arr = numbers.split('');
  const answer = new Set();
  // 같은 숫자의 경우 한 번만 세야 하므로 Set 사용해주기
  
  // 만들 수 있는 모든 순열을 재귀적으로 찾기
  function getPermutation(numbersArray, fixedNumber) {
    if (numbersArray.length) {
      for (let i = 0; i < numbersArray.length; i++) {
        const temp = [...numbersArray];

        // fixedNumber를 제외한 숫자 배열을 재귀함수 호출 시 넘기기 위함
        temp.splice(i, 1);

        if (isPrime(parseInt(fixedNumber + numbersArray[i]))) {
          // 문자열을 parseInt 해서 넣어주어야 '011' 과 '11' 이 같은 숫자로 취급됨
          answer.add(parseInt(fixedNumber + numbersArray[i]));
        }
        getPermutation(temp, fixedNumber + numbersArray[i]);
      }
    }
  }
  
  getPermutation(arr, '');
  return answer.size;
}

splice를 이용해서 고정할 숫자를 하나씩 정하는 게 좋은 해결 방법인 것 같았다.

이 문제의 핵심은 소수 판별보다는 순열 구하기였던 것 같은데 공부하는 김에 순열, 조합을 구하는 코드도 구현해보기로 했다.

🔍 조합 구하기

function getCombinations(array, selectNum) {
  const answer = [];
  if (selectNum === 1) return array.map((value) => [value]);

  // 하나씩 fixedNum으로 삼기
  for (let i = 0; i < array.length; i++) {
    const temp = [...array];
    
    // i번째 인덱스 숫자가 fixedNum이 되면 그 부분까지 잘라냄
    temp.splice(0, i + 1);

    const combinations = getCombinations(temp, selectNum - 1);
    const attached = combinations.map((combination) => [array[i], ...combination]);
    answer.push(...attached);
  }

  return answer;
}

const array = [1, 1, 2, 3, 4];
const result = getCombinations(array, 3);

/* console
[
  [ 1, 1, 2 ], [ 1, 1, 3 ],
  [ 1, 1, 4 ], [ 1, 2, 3 ],
  [ 1, 2, 4 ], [ 1, 3, 4 ],
  [ 1, 2, 3 ], [ 1, 2, 4 ],
  [ 1, 3, 4 ], [ 2, 3, 4 ]
]
*/

🔍 순열 구하기 1

function getPermutations(array, selectNum) {
  const answer = [];
  if (selectNum === 1) return array.map((value) => [value]);

  // 하나씩 fixedNum으로 삼기
  for (let i = 0; i < array.length; i++) {
    const temp = [...array];
    
    // fixedNum 을 제외한 배열을 가지고 순열 구하기
    temp.splice(i, 1);

    const permutations = getPermutations(temp, selectNum - 1);
    const attached = permutations.map((permutation) => [array[i], ...permutation]);
    answer.push(...attached);
  }

  return answer;
}

const example = [1, 2, 3, 4];
const result = getPermutations(example, 3);
console.log(result);

/* console
[
  [ 1, 2, 3 ], [ 1, 2, 4 ],
  [ 1, 3, 2 ], [ 1, 3, 4 ],
  [ 1, 4, 2 ], [ 1, 4, 3 ],
  [ 2, 1, 3 ], [ 2, 1, 4 ],
  [ 2, 3, 1 ], [ 2, 3, 4 ],
  [ 2, 4, 1 ], [ 2, 4, 3 ],
  [ 3, 1, 2 ], [ 3, 1, 4 ],
  [ 3, 2, 1 ], [ 3, 2, 4 ],
  [ 3, 4, 1 ], [ 3, 4, 2 ],
  [ 4, 1, 2 ], [ 4, 1, 3 ],
  [ 4, 2, 1 ], [ 4, 2, 3 ],
  [ 4, 3, 1 ], [ 4, 3, 2 ]
]
*/

순열 구하기는 문제 풀었던 것과 마찬가지로 temp.splice(i, 1)을 이용해서 구현했다.

다만 위 코드는 [1, 1, 2, 3] 와 같이 중복된 숫자가 있는 배열에서 순열을 구할 때 중복된 순열도 포함해버리는 문제가 있다. 첫 번째 1과 두 번째 1이 자리를 바꿔도 다른 순열로 인식해버리기 때문!

[
  [ 1, 1, 2 ], [ 1, 1, 3 ],
  [ 1, 2, 1 ], [ 1, 2, 3 ],
  [ 1, 3, 1 ], [ 1, 3, 2 ],
  [ 1, 1, 2 ], [ 1, 1, 3 ],
  [ 1, 2, 1 ], [ 1, 2, 3 ],
  [ 1, 3, 1 ], [ 1, 3, 2 ],
  [ 2, 1, 1 ], [ 2, 1, 3 ],
  [ 2, 1, 1 ], [ 2, 1, 3 ],
  [ 2, 3, 1 ], [ 2, 3, 1 ],
  [ 3, 1, 1 ], [ 3, 1, 2 ],
  [ 3, 1, 1 ], [ 3, 1, 2 ],
  [ 3, 2, 1 ], [ 3, 2, 1 ]
]

~~정확한 용어를 사용하고 있는 건지는 모르겠지만 무슨 의도인지는 전달되었을 것이라고 믿는다... 🥲~~

🔍 순열 구하기 2 - 중복된 숫자가 있을 때

function getPermutations(array, selectNum) {
  const answer = new Set();
  if (selectNum === 1) return array.map((value) => [value]);

  // 하나씩 fixedNum으로 삼기
  for (let i = 0; i < array.length; i++) {
    const temp = [...array];
    
    // fixedNum 을 제외한 배열을 가지고 순열 구하기
    temp.splice(i, 1);

    const permutations = getPermutations(temp, selectNum - 1);

    const attached = permutations.map((permutation) => parseInt([array[i], ...permutation].join('')));
    attached.forEach((value) => answer.add(value));
  }

  const returnArray = [...answer].map((num) => num.toString().split('').map(s => parseInt(s)));
  return returnArray;
}

const example = [1, 1, 2, 3];
const result = getPermutations(example, 3);
console.log(result);