소인수분해

문제

언어

  • JavaScript

문제 풀이 step 1

  • 주어진 N 에 대해서 소인수 분해를 해야합니다.
  • 첫 번째 해답은 단순하게 2 부터 1 씩 늘려가며 N 에 도달할때 까지 나눠보는 방식입니다.
  • 시간복잡도는 O(N) 으로 N 의 범위가 10000000 으로 충분히 가능합니다.
  • 풀리긴 하지만 조금 느립니다. 한 번 줄여볼까요?? 아래에서 알아보겠습니다.

소스 코드

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

const solution = (input) => {
	const n = parseInt(input[0]);
	let temp = n;
	if (n === 1) return;

	let res = "";
	for (let i = 2; i <= n; i++) {
		while (temp % i === 0) {
			temp /= i;
			res += `${i}\n`;
		}

		if (temp === 1) break;
	}

	console.log(res);
};

solution(input);

시행착오

  • 소수인 수들은 약수가 1 과 자기 자신 밖에 없으므로 소수인 수들은 굳이 약수를 구할 필요가 없습니다.
  • 그래서 주어진 N 이 소수인지 판별하는 코드를 넣어봤습니다. 위의 방식으로 풀었을 때는 288 ms 의 시간이 나왔는데 소수 판별 코드를 넣어보니 1376 ms 의 시간이 나옵니다.
  • 줄여보고자 했지만, 시간이 더 걸린 것을 확인할 수 있었습니다. 아무래도 소수를 판별하는 과정만큼 반복이 늘어나기 때문에 당연한 결과였습니다.

다른 방식의 문제 풀이 step 1

  • 그렇다면 이번에는 첫 번째 방식에서 반복의 수를 줄이는 방식으로 접근해보겠습니다.
  • 반복의 수를 어떻게 줄일 수 있을까요??
    • 우리는 수를 나누다보면 어떤 특이점을 발견하게 됩니다.
    • 예를 들어, 주어진 수가 12 일 때, 약수들을 찾아보면
    • 1 2 3 4 6 12 가 나옵니다.
      • 1 * 12
      • 2 * 6
      • 3 * 4
    • 그리고 위와 같은 형태를 발견할 수 있습니다.
    • 3 을 기점으로 좌우 곱이 대칭되고 있습니다. 즉, 3 이후의 수들 4, 6, 12 는 중복이라서 굳이 나눌 필요가 없다는 것입니다.
    • 그래서 3 까지만 나누기를 하는 방식으로 반복의 수를 줄여볼 수 있겠습니다.
  • 그렇다면 12 를 나눌 수 있는 가장 큰 수는 3 이라고 할 수 있는데, 어떤 수 N 을 나눌 수 있는 가장 큰 수는 무엇일까요??
    • 바로 근호값 입니다.
    • 사실 위 12 의 경우를 좀 더 깊게 본다면
      • 1 * 12
      • 2 * 6
      • 3 * 4
      • 3.xxx * 3.xxx (3.xxx 는 12 의 근호값)
    • 즉, 사실 3 을 기점으로가 아닌 12 의 근호값인 3.xxx 를 기점으로 좌우 곱이 대칭되고 있었던 것입니다.
  • 그래서 결론을 내보자면, 어떤 수 N 을 나눌 수 있는 가장 큰 수는 근호값이라고 볼 수 있겠고, 근호값까지만 반복을 하면 되겠습니다.

다른 방식의 문제 풀이 step 2

  • 그리고 추가적으로 나머지가 있는 경우와 소수인 경우를 처리하면 되겠습니다.
    • 나머지가 있는 경우는 6 이 들어왔을 때 근호값이 2.xxx 까지만 나눠서 2 만 출력이 됩니다. 그래서 나머지를 출력 문자열에 추가해주면 3 도 출력되는 것을 확인할 수 있습니다.
    • 그리고 소수인 경우는 약수를 찾는 과정 속에서 출력 문자열에 아무것도 추가되지 않겠죠. 그래서 자기 자신을 넣어주기 위해서 나머지를 출력 문자열에 추가해주면 됩니다.
    • if (temp > 1) res += ${temp}\n;

소스코드

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

const solution = (input) => {
	const n = parseInt(input[0]);
	let temp = n;
	if (n === 1) return;

	let res = "";
	for (let i = 2; i * i <= n; i++) {
		while (temp % i === 0) {
			temp /= i;
			res += `${i}\n`;
		}

		if (temp === 1) break;
	}
	// 나머지가 있는 경우, 소수인 경우
	if (temp > 1) res += `${temp}\n`;

	console.log(res);
};

solution(input);