문제
https://leetcode.com/problems/permutation-sequence/description/
문제 해결 방식
- 각 자리마다 가능한 순열의 범위는 남은 숫자들로 만들 수 있는 순열의 수로 정해짐
- 현재 선택한 숫자로 만들 수 있는 순열 범위에
k가 속하지 않으면 다음 범위라는 뜻 - 그 범위를 넘어가기 위해
k에서 그 범위(팩토리얼 값)를 빼줌 k가 범위 내에 속할 때까지 반복k가 현재 범위에 속하면, 그 숫자가 확정되고, 해당 숫자를 사용된 것으로 표시- 확정된 숫자는 순열의 일부로 추가되고, 남은 숫자들로 다시 위 과정을 반복해 나머지 자리를 결정
Test Case 예시
예를 들어, n=4일 때 [1, 2, 3, 4]의 숫자로 만들 수 있는 모든 순열을 생각해 봅시다. 총 4! = 24개의 순열이 존재합니다.
첫 번째 자리 선택
첫 번째 자리에는 1, 2, 3, 4 중 하나가 올 수 있고, 첫 번째 숫자를 정하면 그 뒤로 나머지 3자리에 대해 3! = 6개의 순열이 나옵니다.
즉:
- 첫 번째 자리가
1일 때 나오는 순열:1xxxx→ 총 6개 (1 ~ 6번째 순열) - 첫 번째 자리가
2일 때 나오는 순열:2xxxx→ 총 6개 (7 ~ 12번째 순열) - 첫 번째 자리가
3일 때 나오는 순열:3xxxx→ 총 6개 (13 ~ 18번째 순열) - 첫 번째 자리가
4일 때 나오는 순열:4xxxx→ 총 6개 (19 ~ 24번째 순열)
이제 예를 들어, k=9번째 순열을 구한다고 해봅시다.
- 첫 번째 자리가
1이면, 순열은1xxxx에서 나오는데 이는 1~6번째 순열에 해당하므로,k=9는 그 범위에 포함되지 않습니다. 그래서 첫 번째 자리는1이 아니고, 우리는 그 범위를 넘어가야 하므로k=9 - 6 = 3으로 갱신합니다. - 첫 번째 자리가
2이면, 순열은2xxxx에서 나오는데 이는 7~12번째 순열입니다. 여기서k=3은 해당 범위에 포함되므로, 첫 번째 자리는2가 됩니다.
이 과정을 통해 첫 번째 자리를 결정한 것입니다.
두 번째 자리 선택
이제 첫 번째 자리가 2로 결정됐고, 나머지 자리의 숫자는 [1, 3, 4]입니다. 이제 두 번째 자리를 정해야 합니다.
남은 3자리에서 가능한 순열의 개수는 2! = 2입니다. 즉:
- 두 번째 자리가
1일 때 나오는 순열:21xxx→ 총 2개 (7~8번째 순열) - 두 번째 자리가
3일 때 나오는 순열:23xxx→ 총 2개 (9~10번째 순열)
현재 k=3이므로, 두 번째 자리는 1이 아닌 3이 됩니다. 따라서 k=3 - 2 = 1로 갱신됩니다.
나의 코드
class Solution {
public String getPermutation(int n, int k) {
String ans = "";
boolean[] vis = new boolean[n + 1]; // 숫자 사용 여부
// n개의 숫자를 사용하여 순열을 구성
for (int i = 0; i < n; ++i) {
int fact = 1; // 현재 자리에서 고려할 남은 자리수에 대한 팩토리얼을 계산
// 남은 자리에 대한 팩토리얼 계산
for (int j = 1; j < n - i; ++j) {
fact *= j;
}
// 1부터 n까지의 숫자 중에서 순열을 선택
for (int j = 1; j <= n; ++j) {
// j가 아직 사용되지 않았다면
if (!vis[j]) {
// 현재 자리의 팩토리얼보다 k가 크다면, 해당 순열 조합은 현재 범위를 넘어가므로 넘겨줌
if (k > fact) {
k -= fact; // 해당 범위를 넘어갔으므로 k에서 팩토리얼 값을 빼줌
} else {
// 현재 자리에 j를 넣음
ans += j;
vis[j] = true;
break; // 현재 자리에 숫자를 채웠으므로 다음 자리로 이동
}
}
}
}
return ans; // 최종적으로 완성된 순열 반환
}
}