집합이 [1, 2, 3, ..., n]과 같을 때, 이 집합은 총 n!개의 서로 다른 순열을 가집니다. 모든 순열을 나열하고 순서대로 번호를 붙이면 n = 3일 때 다음과 같은 시퀀스를 얻습니다.
["123", "132", "213", "231", "312", "321"]
따라서 n과 k가 주어졌을 때, k번째 순열 시퀀스를 반환해야 합니다. 여기서 n은 1부터 9까지(포함), k는 1부터 n!까지(포함)의 범위를 가집니다. 예를 들어 n = 4, k = 9가 주어지면 결과는 "2314"가 됩니다.
문제 해결 접근 방식
모든 순열을 생성한 후 k번째를 찾는 비효율적인 방법 대신, 팩토리얼의 성질을 활용하면 각 자리의 숫자를 수학적으로 결정할 수 있습니다. n자리 순열에서 첫 번째 자리에 오는 숫자 하나당 (n-1)!개의 순열이 존재합니다. 이 원리를 이용하면 k를 기준으로 각 자리에 올 숫자를 차례대로 계산할 수 있습니다.
알고리즘 단계
- 빈 문자열 ans를 선언하고, 크기가 n인 후보(candidates) 배열을 정의합니다.
- i가 0부터 n-1까지 반복하며 candidates[i]에 ((i + 1) + '0')을 저장하여 숫자 문자를 채웁니다.
- 크기가 n+1인 팩토리얼 배열 fact를 만들고 fact[0] := 1로 초기화합니다.
- i가 1부터 n까지 반복하며 fact[i] := fact[i - 1] * i로 팩토리얼 값을 계산합니다.
- k를 1 감소시킵니다. (0 기반 인덱스로 변환)
- i를 n-1부터 0까지 역순으로 반복합니다.
- idx := k / fact[i] 로 현재 자리에 올 숫자의 인덱스를 구합니다.
- ans := ans + candidates[idx] 로 해당 숫자를 결과에 추가합니다.
- j가 idx부터 시작해 j + 1 < candidates 크기인 동안 candidates[j] := candidates[j + 1]로 배열을 왼쪽으로 한 칸씩 당겨 사용된 숫자를 제거합니다.
- k := k mod fact[i] 로 남은 순열 위치를 갱신합니다.
- ans를 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
string getPermutation(int n, int k) {
string ans = "";
vector <char> candidates(n);
for(lli i = 0; i < n; i++)
candidates[i] = ((i + 1) + '0');
vector <lli> fact(n + 1);
fact[0] = 1;
for(lli i = 1; i <= n; i++)
fact[i] = fact[i - 1] * i;
k--;
for(lli i = n - 1; i >= 0; i--){
lli idx = k / fact[i];
ans += candidates[idx];
for(lli j = idx; j + 1 < candidates.size(); j++)
candidates[j] = candidates[j + 1];
k = k % fact[i];
}
return ans;
}
};
main(){
Solution ob;
cout << ob.getPermutation(4, 9);
}입력
4 9
출력
2314
동작 원리 설명
n = 4, k = 9인 경우를 살펴보겠습니다. 먼저 k를 1 감소시켜 8로 만듭니다. 첫 번째 자리에서는 3! = 6개의 순열이 각 숫자마다 존재하므로, idx = 8 / 6 = 1이 되어 두 번째 후보인 '2'가 선택됩니다. 이후 k = 8 % 6 = 2로 갱신되고, 같은 방식으로 다음 자리들을 결정하면 최종적으로 "2314"를 얻게 됩니다.
이 알고리즘은 팩토리얼 계산에 O(n), 각 자리 선택 및 배열 재정렬에 O(n²)의 시간 복잡도를 가지므로, n이 최대 9인 조건에서 매우 효율적으로 동작합니다.