1보다 큰 수 n이 주어졌을 때, 이 수의 모든 소인수(素因數)를 찾아 정렬된 순서로 반환하는 문제를 생각해 봅시다. 어떤 수는 소수들의 곱으로 표현할 수 있으며, 이때 곱해지는 소수들이 바로 그 수의 소인수입니다. 같은 소인수가 여러 번 나타날 수도 있다는 점에 유의해야 합니다.
예를 들어 입력이 42라면, 출력은 다음과 같습니다.
[2, 3, 7]
문제 해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 결과를 저장할 빈 리스트
res를 생성합니다. n이 2로 나누어떨어지는 동안 반복합니다.res의 끝에 2를 추가합니다.n을n / 2의 몫으로 갱신합니다.
- 3부터 √n까지 2씩 증가시키며 반복합니다.
n이i로 나누어떨어지는 동안res에i를 추가하고,n을n / i의 몫으로 갱신합니다.
- 반복 종료 후
n이 2보다 크면, 남은n자체가 소수이므로res에 추가합니다. res를 반환합니다.
구현 예제
아래 파이썬 코드를 통해 더 잘 이해할 수 있습니다.
class Solution: def solve(self, n): res = [] while n % 2 == 0: res.append(2) n //= 2 for i in range(3, int(n**0.5) + 1, 2): while n % i == 0: res.append(i) n //= i if n > 2: res.append(n) return res ob = Solution() print(ob.solve(42))
입력
42
출력
[2, 3, 7]
동작 원리 살펴보기
입력값이 42일 때 알고리즘은 다음과 같이 진행됩니다.
- 42는 2로 나누어떨어지므로 2를 추가하고, 21이 됩니다. 21은 2로 나누어떨어지지 않으므로 첫 번째 반복을 종료합니다.
- 3부터 √21(약 4.58)까지 홀수만 검사합니다. 21은 3으로 나누어떨어지므로 3을 추가하고, 7이 됩니다.
- 루프가 끝난 후 남은 값 7은 2보다 큰 소수이므로 결과에 추가합니다.
- 최종적으로
[2, 3, 7]이 반환되며, 이미 작은 인수부터 처리하므로 결과는 항상 정렬된 상태가 됩니다.
이 알고리즘은 시행 나눗셈(Trial Division) 방식으로, 시간 복잡도는 O(√n)입니다. 2를 먼저 제거한 후 홀수만 검사하기 때문에 연산 횟수를 절반 가까이 줄일 수 있다는 장점이 있습니다.