프로그래머스 LV.0 소인수분해

프로그래머스 LV.0 소인수분해

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

프로그래머스

 

1. 문제 명

소인수분해

2. 문제 설명

소인수분해란 어떤 수를 소수들의 곱으로 표현하는 것입니다. 예를 들어 12를 소인수 분해하면 2 * 2 * 3 으로 나타낼 수 있습니다. 따라서 12의 소인수는 2와 3입니다. 자연수 n이 매개변수로 주어질 때 n의 소인수를 오름차순으로 담은 배열을 return하도록 solution 함수를 완성해주세요.

3. 제한 사항

- 2 ≤ n ≤ 10,000

4. 예시

n	result
12	[2, 3]
17	[17]
420	[2, 3, 5, 7]

5. 기본 제공 코드

function solution(n) {
    var answer = [];
    return answer;
}

6. 제출한 내 답

const solution = (n) => {
  let answer = [];

  for (i = 2; i <= n; i++) {
    if (n % i === 0) {
      answer.push(i);
    }
  }

  if (answer.length === 0) {
    return [n];
  } else {
    return answer.filter((v) => {
      for (i = 2; i <= Math.sqrt(v); i++) {
        if (v % i === 0) {
          return false;
        }
      }
      return true;
    });
  }
};

 

6-2. VSC에 작성한 내용

const solution = (n) => {
  let answer = [];

  for (i = 2; i <= n; i++) {
    if (n % i === 0) {
      answer.push(i);
    }
  }

  if (answer.length === 0) {
    return [n];
  } else {
    return answer.filter((v) => {
      for (i = 2; i <= Math.sqrt(v); i++) {
        if (v % i === 0) {
          return false;
        }
      }
      return true;
    });
  }
};

// 테스트
console.log(solution(2));
console.log(solution(12));
console.log(solution(17));
console.log(solution(420));
console.log(solution(169));
console.log(solution(10000));

7. 특이사항

고치기 전 코드

const solution = (n) => {
  let answer = [];

  for (i = 2; i <= Math.sqrt(n); i++) {
    if (n % i === 0) {
      answer.push(i);
    }
  }
...

};

처음엔 배열 answer에 들어갈 요소 고르기를 소수인지 검사하는 방식으로 진행했었다

이 경우 n의 제곱근 이상의 수에 대해서는

해당 수가 소수인지 아니면 더 소인수분해가 가능한 수인지 확인할 수가 없다.

 

이를 고쳐서

2부터 n까지 중 n이 나누어떨어지는 수가 없다면 n을 그대로 리턴하고,

나누어 떨어지는 수(약수)들이 있다면 이들을 한번더 소수인지(소인수분해가 가능한지) 검사한다

 

코드를 고치고 보니 이제 이해가 간다

 

8. 다른 사람이 작성한 답

8-1. 가장 많이 쓰인 풀이법

function solution(n) {
    var answer = [];

    for(let i = 2; i <= n; i++) {

        while (n % i === 0) {

            n = n / i;
            answer.push(i);

        }
    }

    return [...new Set(answer)];
}