[Level2] 23. 소수 찾기

in 코딩테스트 on 프로그래머스




프로그래머스 2단계 문제는 사실 아직도 내게 살짝 버겁다. (특히 카카오!)
초반에 하루 3문제라는 기준을 잡았던 터라, 나에게 투자가능한 공부시간 대비 3문제를 완벽하게 이해하고 넘어갈 시간이 부족했다.
그래서 오래 고민하지 못하고, 어느정도의 시간이 지나면 솔루션을 확인햇고, 그 솔루션에 대한 깊은 이해도 하지 못하고 넘어갔다.
3문제를 해결한다는 것에만 집착하고 온전히 내 것으로 만들진 못한 것이다.
그래서 이제부터는 문제 갯수에 집착하지 않고, 1문제라도 그 문제에 관련된 자료구조, 알고리즘을 정확히 이해하는데 집중하도록 하자.
나에게 중요한 것은 문제를 만났을 때 스스로 해결할 수 있는 문제 해결 능력임을 잊지 말자.👊


95. 소수 찾기

프로그래머스 

function getPermutation(arr, selectNum) {
  let answer = [];

  if (selectNum === 1) return arr.map((value) => [value]);

  arr.forEach((arrValue, index, origin) => {
    let rest = [...origin.slice(0, index), ...origin.slice(index + 1)];
    let permutation = getPermutation(rest, selectNum - 1);
    let attach = permutation.map((permValue) => [arrValue, ...permValue]);
    answer.push(...attach);
  });

  return answer;
}

function demicalCheck(num) {
  if (num === 1 || num === 0) return false;
  for (let i = 2; i ** 2 <= num; i++) {
    if (num % i === 0) return false;
  }
  return true;
}

function solution(num) {
  let answer = [];
  let split = num.split("");
  for (let i = 1; i <= split.length; i++) {
    answer.push(...getPermutation(split, i));
  }
  for (let i = 0; i < answer.length; i++) {
    answer[i] = answer[i].join("") / 1;
  }

  answer = [...new Set(answer)];
  return answer.filter((value) => demicalCheck(value) === true).length;
}

console.log(solution("011"));



완전 탐색

  • 생길 수 있는 모든 경우의 수에 대해서 조건이 성립하는지를 알아보는 행위 그 자체.
  • 완전 탐색시, 완전 탐색 할 대상에 대해서 자료형을 구축해야 한다.
  • dfs, 그래프, 순열과 조합이 주로 사용된다.



조합

1,2,3,4 의 숫자를 중복을 허용하지 않고, 순서 구분 없이 3개로 구성할 수 있는 방법은?

input: [1,2,3,4]
ouput: [[1,2,3],[1,2,4],[1.3.4].[2,3,4]]

이러한 경우가 4C3 이다.
4개중 3개를 선택할 때 나올 수 있는 모든 조합을 구한 다는 것. (순서 상관 x)
[1,2,3]과 [1,3,2]는 같은 것으로 취급한다.

어떻게 구현하지?

- 1을 선택하고 나머지 3개중 2개를 선택한다. [1,2,3] [1,2,4] [1,3,4]
- 2를 선택하고 나미저 3개중 2개를 선택한다. [2,3,4]
- 3을 선택하고 나머지 3개중 2개를 선택한다. .
- 4를 선택하고 나머지 3개중 2개를 선택한다. .
  • 배열의 처음부터 1개씩 고정하고, 나머지 뒷 배열에 대한 조합을 구한다.
  • 조합에 대한 조합 > 재귀로 해결


function getCombination(arr, selectNum) {
  let answer = [];

  // 1개씩 고를 때는 각각의 수를 배열로 변환하여 반환한다.
  if (selectNum === 1) return arr.map((value) => [value]);

  arr.forEach((arrValue, index, origin) => {
    let rest = origin.slice(index + 1); // 해당하는 인덱스의 뒷 배열들
    // 뒷 배열들에 대한 조합을 재귀로 처리
    let combination = getCombination(rest, selectNum - 1);
    // 재귀로 구한 뒷부분 배열 붙이기
    let attach = combination.map((comValue) => [arrValue, ...comValue]);
    answer.push(...attach);
  });

  return answer;
}

let example = [1, 2, 3, 4];
console.log(getCombination(example, 3));
//[ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 4 ], [ 2, 3, 4 ] ]



순열

  • 순열은 조합의 확장된 개념이다.
  • 이제는 4개중 3개를 구할 때, 순서가 다르면 다른 값으로 취급한다.
  • [1,2,3]과 [1,3,2]는 다른 값으로 취급한다.


nPr = nCr * r!

아까 구했던 조합 값을 가져와보자.

[ 1, 2, 3 ] => 순서를 바꾸는 경우의 수 = 3!
[ 1, 2, 4 ] => 순서를 바꾸는 경우의 수 = 3!
[ 1, 3, 4 ] => 순서를 바꾸는 경우의 수 = 3!
[ 2, 3, 4 ] => 순서를 바꾸는 경우의 수 = 3!

따라서 순열은 조합에 해당 기능을 추가해주기만 하면 된다.

function getPermutation(arr, selectNum) {
  let answer = [];

  // 1개씩 고를 때는 각각의 수를 배열로 변환하여 반환한다.
  if (selectNum === 1) return arr.map((value) => [value]);

  arr.forEach((arrValue, index, origin) => {
    let rest = [...origin.slice(0, index), ...origin.slice(index+1)]; // 해당 인덱스를 제거한 배열
    // 뒷 배열들에 대한 순열을 재귀로 처리
    let permutation = getPermutation(rest, selectNum - 1);
    // 재귀로 구한 뒷부분 배열 붙이기
    let attach = permutation.map((permValue) => [arrValue, ...permValue]);
    answer.push(...attach);
  });

  return answer;
}

let example = [1, 2, 3, 4];
console.log(getPermutation(example, 3));
// [
//   [ 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 ]
// ]