프로그래머스 입문 120852 소인수분해
문제
자연수 n이 매개변수로 주어질 때, n의 소인수를 오름차순으로 담은 배열을 반환한다.
| n | result |
|---|---|
| 12 | [2, 3] |
| 17 | [17] |
| 420 | [2, 3, 5, 7] |
풀이
제곱근 범위에서 소인수 찾기
#include <stdlib.h>
int* solution(int n)
{
enum { MAX_FACTOR_COUNT = 16 };
int* factors = (int*)malloc(sizeof(int) * MAX_FACTOR_COUNT);
int factor_count = 0;
int remaining = n;
for (int divisor = 2; divisor * divisor <= remaining; divisor++)
{
if (remaining % divisor == 0)
{
factors[factor_count++] = divisor;
remaining /= divisor;
while (remaining % divisor == 0)
{
remaining /= divisor;
}
}
}
if (remaining > 1)
{
factors[factor_count++] = remaining;
}
return factors;
}60을 소인수 분해하면 2 * 2 * 3 * 5이다.
divisor = 2부터 반복문을 돌면서 remaining을 나눈다.
소인수를 찾아야 하는데 divisor가 4가 되면 어떻게 되는지 의아할 수 있다.
하지만 그 고민은 divisor가 2일 때 이미 해결되었다.
4는 2의 배수이고, while 문에서 remaining을 2로 더 이상 나누어 떨어지지 않을 때까지 나누기 때문이다.
따라서 이후 remaining에는 2의 배수가 남아 있지 않다.
2로 모두 나누고 나면 remaining은 15가 된다.
그다음 divisor가 3이 되고, 3으로 나누면 remaining은 5가 된다.
이때 다음 divisor인 4는 4 * 4 <= 5를 만족하지 못하므로 반복문이 종료된다.
for 문의 조건식을 divisor <= remaining이 아니라 divisor * divisor <= remaining으로 작성하는 이유는 다음과 같다.
어떤 수의 약수는 곱해서 원래 수가 되는 (작은 약수, 큰 약수) 형태의 쌍으로 묶을 수 있고, 그중 작은 약수는 반드시 그 수의 제곱근 이하가 된다.
그래서 divisor * divisor > remaining이 되는 순간부터는 자기 자신을 제외한 새로운 약수를 찾을 수 없다.
예를 들어 20의 약수는 1, 2, 4, 5, 10, 20으로 6개다.
이를 곱해서 20이 되는 쌍으로 묶으면 (1, 20), (2, 10), (4, 5)가 된다.
√20의 근사치는 4.47이므로 작은 약수는 모두 4.47 이하에 있다.
따라서 5 * 5 > 20이 되는 시점부터는 20 자기 자신을 제외한 새로운 약수를 찾을 수 없다.
이 코드는 divisor * divisor <= remaining인 동안만 반복하므로 마지막 소인수를 반복문 안에서 직접 만나지 못할 수 있다.
예를 들어 앞의 60 예시에서는 remaining이 5가 된 뒤 다음 divisor인 4에서 반복문이 종료된다.
그래서 5는 아직 factors에 저장되지 않은 상태로 남는다.
이때 남은 remaining이 1보다 크다면 그 값은 마지막 소인수다.
왜냐하면 이 값이 소수가 아니라면 앞에서 더 작은 약수로 나누어졌어야 하는데, 그런 약수는 반복문에서 이미 확인했기 때문이다.
따라서 remaining > 1이면 remaining도 factors에 저장한다.
마지막 if 문 때문에 처음에는 흐름이 조금 낯설 수 있지만, 이 코드의 좋은 점은 안쪽 while 문까지 포함해도 시간 복잡도가 최악의 경우 O(√n)이라는 점이다.
안쪽 while 문은 실행될 때마다 remaining을 최소 2로 나누므로 전체 반복 횟수는 최대 O(log n)이다.
최악의 경우는 n이 소수라서 remaining이 줄어들지 않고, 바깥 반복문이 √n까지 후보 약수를 확인하는 경우다.
끝까지 나누며 소인수 찾기
#include <stdlib.h>
int* solution(int n)
{
enum { MAX_FACTOR_COUNT = 16 };
int* factors = (int*)malloc(sizeof(int) * MAX_FACTOR_COUNT);
int factor_count = 0;
for (int divisor = 2; divisor <= n; divisor++)
{
if (n % divisor == 0)
{
factors[factor_count++] = divisor;
while (n % divisor == 0)
{
n /= divisor;
}
}
}
return factors;
}이 코드는 divisor를 2부터 n까지 하나씩 증가시키며 나누어 떨어지는 값을 찾는다.
나누어 떨어지는 divisor를 찾으면 그 값은 소인수이므로 factors에 저장한다.
그다음 n이 같은 divisor로 나누어 떨어지는 동안 계속 나누어, n에 남아 있는 해당 소인수를 모두 제거한다.
첫 번째 풀이와 달리 반복 조건이 divisor <= n이라서, n이 나누어 떨어져 1이 될 때까지 반복문 안에서 계속 처리된다.
그래서 반복문이 끝난 뒤 이전 풀이처럼 별도의 if문으로 남은 값을 검사할 필요가 없다.
코드 흐름은 더 단순해 보이지만, 시간 복잡도는 최악의 경우 O(n)이다.
n이 소수이면 한 번도 나누어지지 않기 때문에 2부터 n까지 모든 후보 약수를 확인한다.