1부터 n까지의 숫자를 나열하는 모든 순열(permutation) 중에서 소수(prime)는 반드시 소수 번째 위치에 놓이도록 배치해야 하는 문제입니다. 정답은 매우 커질 수 있으므로 109 + 7로 나눈 나머지를 반환해야 합니다.
예를 들어 n = 5라면 정답은 12입니다. 유효한 순열의 한 예는 [1, 2, 5, 4, 3]이며, [5, 2, 3, 4, 1]은 잘못된 순열입니다. 값 5가 1번째 자리에 놓였는데, 1은 소수가 아니기 때문입니다.
문제 접근 방법
이 문제의 핵심 아이디어는 조합론에 있습니다. 소수끼리의 자리 배치와 비소수끼리의 자리 배치는 서로 독립적이므로, 두 경우의 수를 곱하면 전체 답을 구할 수 있습니다.
- 1부터 n 사이의 소수 개수를 세서 x라고 합니다.
- x개의 소수는 x개의 소수 위치에 임의로 배치할 수 있으므로 x!가지 경우가 있습니다.
- 나머지 (n - x)개의 비소수 역시 (n - x)!가지 방법으로 배치할 수 있습니다.
- 따라서 전체 경우의 수는 x! × (n - x)!이며, 이를 10^9 + 7로 나눈 나머지를 구하면 됩니다.
알고리즘 단계
- getNum이라는 메서드를 정의합니다.
- primes := 2부터 100까지의 모든 소수 목록
- i := 0으로 초기화
- i가 소수 목록의 길이보다 작은 동안 반복:
- 만약 primes[i] > n이면 i를 반환 (n 이하의 소수 개수)
- i를 1 증가
- 반복문이 끝나면 소수 목록의 전체 길이를 반환
- 본 문제는 다음과 같이 해결합니다:
- x := getNum(n), p := 1, m := 10^9 + 7
- i를 x부터 1까지 감소시키며 p := p × i, p := p mod m 연산 수행
- i를 (n - x)부터 1까지 감소시키며 같은 연산 수행
- 최종적으로 p를 반환
파이썬 구현 예제
아래 구현을 통해 더 잘 이해해 보겠습니다.
class Solution(object):
def getNum(self, n):
primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
i = 0
while i < len(primes):
if primes[i] > n:
return i
i += 1
return len(primes)
def numPrimeArrangements(self, n):
"""
:type n: int
:rtype: int
"""
x = self.getNum(n)
p = 1
m = 1000000000 + 7
for i in range(x, 0, -1):
p *= i
p %= m
for i in range(n - x, 0, -1):
p *= i
p %= m
return p
ob1 = Solution()
print(ob1.numPrimeArrangements(100))입력
100
출력
682289015
코드 설명 및 복잡도 분석
n = 100일 때 1부터 100 사이의 소수는 총 25개입니다. 따라서 정답은 25! × 75!를 10^9 + 7로 나눈 나머지인 682289015가 됩니다.
getNum 메서드는 미리 준비된 소수 목록을 한 번만 순회하므로 사실상 상수 시간에 동작하고, 팩토리얼 계산은 최대 n번의 곱셈과 나머지 연산을 수행합니다. 따라서 전체 시간 복잡도는 O(n)이며, 공간 복잡도는 O(1)입니다.