75. 소수찾기 Javascript

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

프로그래머스

 

 

1. 문제에 대한 이해

• 우리가 풀어야 할 문제는 무엇인가?
   - 종이 조각으로 만들 수 있는 소수가 몇 개인지 구하라
• 주어진 자료는 무엇인가?
   - numbers : 각 종이 조각에 적힌 숫자가 적힌 문자열
• 조건은 무엇인가?
   - numbers는 길이 1 이상 7 이하인 문자열입니다.
   - numbers는 0~9까지 숫자만으로 이루어져 있습니다.

2. 계획

• 전에 비슷한 문제를 알고 있는가?
• 이 문제를 푸는데 있어서 유용하게 쓸 수 있는 지식은 무엇인가?
• 비슷한 문제를 풀어본 적이 있다면 그 것을 활용할 수 있는가?
• 만약 문제를 풀 수 없다면 문제를 더 단순하게 하기 위해서 주어진 조건을 버려보아라

1. 주어진 문자열을 나눠서 배열로 만든다
2. 숫자를 조합해서 만들 수 있는 모든 수를 구한다
3. 소수 찾는 방법을 만든다.
4. 이 숫자들을 순회하면서 소수인지 아닌지 확인하고
5. 소수이면 빈 배열에 넣어준다.
6. 이 배열의 길이를 리턴한다.

3. 실행

• 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.

const findPrime = (numbers) => {
  const set = new Set(numbers);
  const uniqueNumbers = [...set];

  let primeCount = 0;

  for (i = 0; i < uniqueNumbers.length; i++) {
    let isNotPrime = false;
      for (j = 2; j <= Math.floor(Math.sqrt(uniqueNumbers[i])); j++) {
        if (uniqueNumbers[i] % j === 0) {
          isNotPrime = true;
        } 
      }
    if (isNotPrime === false) {
      primeCount += 1;
    }
  }
    return primeCount;
};


const solution = (string) => {
  const strArr = [...string];
  function getPermutations(strArr, numberOfPermutations) {
    if (numberOfPermutations === 0) {
      return [];
    }

    if (numberOfPermutations === 1) {
      return strArr.map(number => [number]);
    }

    const permutations = [];
    for (let i = 0; i < strArr.length; i++) {
      const number = strArr[i];
      const remainingNumbers = strArr.slice(0, i).concat(strArr.slice(i + 1));
      const subPermutations = getPermutations(remainingNumbers, numberOfPermutations - 1);
      subPermutations.forEach(subPermutation => {
        permutations.push([number].concat(subPermutation));
      });
    }

    return permutations;
  }

  const result = [];
  for (let i = 0; i < strArr.length; i++) {
    result.push(getPermutations(strArr, i + 1));
  }

  return findPrime(result.flat().map(arr => Number(arr.join(''))).filter(num => num !== 1 && num !== 0));
};

test('findPrime', () => {
  expect(solution('17')).toEqual(3);
  expect(solution('011')).toEqual(2);
});

 

계획은 쉽게 세웠는데 계획대로 코드를 작성하는게 힘들었다. 
우선, 주어진 숫자로 만들 수 있는 모든 경우의 수를 구하는게 어려웠다.
조금 찾아보니 알고리즘 순열을 이용하는 문제였던것 같다. 
순열에 대해서 이해는 했는데 이걸 코드로 구현하려니까 막막했다. 
다른 사람의 코드를 조금 참고해서 모든 경우의 수를 구하는 배열을 만들었고 
이 배열을 소수 구하는 함수에 넘겨서 소수의 개수를 찾는 방식으로 문제를 해결했다. 
어떻게 리팩토링 할 수 있을지 좀 더 고민해봐야겠다.