문제 개요
소문자로만 이루어진 길이 m인 문자열이 주어졌을 때, 이 문자열에서 만들 수 있는 모든 순열을 사전식(lexicographic) 순서로 정렬했을 때 n번째 순열을 찾는 문제입니다.
예를 들어 문자열이 "pqr"이고 n = 3이라면, 전체 순열은 [pqr, prq, qpr, qrp, rpq, rqp]처럼 정렬된 순서로 나열되므로 세 번째인 "qpr"이 결과가 됩니다.
해결 접근 방법
모든 순열을 직접 생성하는 것은 비효율적이므로, 각 자리에 올 수 있는 문자를 결정하면서 남은 순열의 개수를 계산(다항계수 활용)하여 n번째 순열을 효율적으로 찾습니다. 알고리즘의 핵심 단계는 다음과 같습니다.
- 팩토리얼 값을 미리 계산해 배열에 저장합니다.
- 문자열의 각 알파벳 등장 횟수를 occurrence 배열에 기록합니다.
- 각 위치(k번째 자리)마다 'a'부터 'z'까지 차례로 시도하며, 해당 문자를 고정했을 때 만들어지는 순열의 개수를 팩토리얼 조합으로 계산합니다.
- 누적합(Sum)이 n 이상이 되면 그 문자가 현재 자리에 확정되고, n을 갱신한 뒤 다음 자리로 넘어갑니다.
- 남은 문자들은 사전식 순서대로 뒷자리에 채워 넣습니다.
구현 예제
아래는 위 알고리즘을 파이썬으로 구현한 코드입니다.
MAX_CHAR = 26
MAX_FACT = 20
factorials = [None] * (MAX_FACT)
def get_nth_permute(string, n):
factorials[0] = 1
for i in range(1, MAX_FACT):
factorials[i] = factorials[i - 1] * i
size = len(string)
occurrence = [0] * (MAX_CHAR)
for i in range(0, size):
occurrence[ord(string[i]) - ord('a')] += 1
res = [None] * (MAX_CHAR)
Sum = 0
k = 0
while Sum != n:
Sum = 0
for i in range(0, MAX_CHAR):
if occurrence[i] == 0:
continue
occurrence[i] -= 1
temp_sum = factorials[size - 1 - k]
for j in range(0, MAX_CHAR):
temp_sum = temp_sum // factorials[occurrence[j]]
Sum += temp_sum
if Sum >= n:
res[k] = chr(i + ord('a'))
n -= Sum - temp_sum
k += 1
break
if Sum < n:
occurrence[i] += 1
i = MAX_CHAR - 1
while k < size and i >= 0:
if occurrence[i]:
res[k] = chr(i + ord('a'))
occurrence[i] -= 1
i += 1
k += 1
i -= 1
return ''.join(res[:k])
n = 3
string = "pqr"
print(get_nth_permute(string, n))입력
"pqr", n = 3
출력
qpr
동작 원리 설명
이 코드의 핵심은 중복 문자가 있는 경우에도 올바르게 동작한다는 점입니다. 특정 문자를 현재 자리에 배치했을 때 나머지 문자들로 만들 수 있는 순열의 개수는 다음 공식으로 계산됩니다.
(전체 남은 자릿수 - 1)! ÷ (각 문자별 남은 개수의 팩토리얼 곱)
이 값을 누적하며 n과 비교함으로써, 실제로 모든 순열을 생성하지 않고도 n번째 순열을 O(26 × m) 수준의 반복으로 빠르게 찾아낼 수 있습니다. 마지막 while 루프는 남은 문자들을 역순(사전식 순서 유지)으로 채워 최종 결과를 완성합니다.