문제 설명
두 개의 값 n과 k가 주어졌을 때, 1부터 n까지의 숫자 목록 [1, 2, ..., n]을 사전순(lexicographic order)으로 배열해 생성되는 모든 순열 중에서 k번째 순열을 문자열 형태로 찾는 것이 목표입니다.
예를 들어 n = 4라면 아래와 같이 총 24개(4!)의 순열이 순서대로 만들어집니다.
[1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321]
따라서 입력이 n = 4, k = 5라면 출력은 "1432"가 됩니다.
해결 접근 방법
이 문제는 팩토리얼 진법(factorial number system)을 이용하면 모든 순열을 일일이 생성하지 않고도 k번째 순열을 바로 계산할 수 있습니다. k를 팩토리얼 진법으로 변환하면 각 자릿수가 남은 숫자 중 어떤 인덱스의 원소를 선택할지 결정하는 역할을 하게 됩니다.
1단계: factors() 함수 정의
factors() 함수는 주어진 수를 팩토리얼 진법의 자릿수들로 변환합니다. 동작 과정은 다음과 같습니다.
매개변수 num을 받습니다.
quo := num으로 초기화합니다.
res := 양쪽 끝에서 삽입·삭제가 가능한 덱(deque)을 생성하고 0을 넣어 초기화합니다.
i := 2로 초기화합니다.
quo가 0이 될 때까지 반복합니다.
- quo를 i로 나눈 몫과 나머지를 구합니다(quo := 몫, rem := 나머지)
- rem을 res의 앞쪽에 삽입합니다
- i를 1 증가시킵니다res를 반환합니다.
2단계: 메인 로직 수행
1부터 n까지의 값을 담은 리스트 numbers를 만듭니다.
결과를 저장할 빈 문자열 res를 준비합니다.
k_fact := factors(k)로 k의 팩토리얼 진법 표현을 구합니다.
k_fact의 길이가 numbers의 길이보다 짧은 동안, numbers의 첫 번째 원소를 문자열로 변환해 res에 이어 붙인 뒤 리스트에서 제거합니다.
k_fact의 각 자릿수를 인덱스로 사용해 numbers에서 해당 위치의 원소를 꺼내 res에 추가합니다.
완성된 res를 반환합니다.
구현 코드
위 알고리즘은 다음과 같은 파이썬 코드로 구현할 수 있습니다.
from collections import deque
def factors(num):
quo = num
res = deque([0])
i = 2
while quo:
quo, rem = divmod(quo, i)
res.appendleft(rem)
i += 1
return res
class Solution:
def solve(self, n, k):
numbers = [num for num in range(1, n + 1)]
res = ""
k_fact = factors(k)
while len(k_fact) < len(numbers):
res += str(numbers.pop(0))
for index in k_fact:
number = numbers.pop(index)
res += str(number)
return res
ob = Solution()
n = 4
k = 5
print(ob.solve(n, k))
실행 결과
입력:
4, 5
출력:
1432
동작 원리 살펴보기
n = 4, k = 5인 경우 factors(5)는 [2, 1, 0]을 반환합니다. k_fact의 길이(3)가 numbers의 길이(4)보다 짧으므로 첫 번째 숫자 1이 먼저 결과에 고정됩니다. 이후 인덱스 2, 1, 0을 차례대로 적용하면 남은 숫자 [2, 3, 4]에서 4 → 3 → 2 순서로 선택되어 최종적으로 "1432"가 완성됩니다. 이처럼 팩토리얼 진법을 활용하면 n!개의 순열을 전부 생성하지 않고도 원하는 순열을 효율적으로 직접 구할 수 있습니다.