줄서는 방법
이 문제는 길이가 N인 수열 중에서 K번째 수열을 구하는 문제이다.
문제를 보자마자, 아래와 같은 이미지가 떠올랐다.
함정같지만 뾰족하게 떠오르는 풀이법이 없어, 단순하게 1번째 수열부터 K번째 수열까지 백트래킹으로 찾아보려 했지만, 당연히 시간 초과가 발생했다.
왜냐하면, N이 최대 20까지 주어질 수 있고, 이때 가능한 경우의 수는 20! 가지가 되기 때문에 무식한 완전 탐색 방식은 사용할 수 없었다.
핵심 아이디어: 수열의 경우의 수 = N!
우선, 길이가 N인 수열의 경우의 수가 N!이라는 것을 이해해야 한다.
- 첫 번째 자리에 올 수 있는 수는 N개
- 두 번째 자리는 N - 1개 (첫 번째 수 사용 제외)
- 세 번째 자리는 N - 2개
- ...
- 마지막 자리는 1개
즉, 전체 경우의 수는:
이 원리를 바탕으로, 각 자리에 올 수 있는 수를 조합적으로 계산해서 바로 K번째 수열을 구할 수 있다.
K번째 수열 구하기 예시 (N = 5, K = 113)
- (N-1)! = 4! = 24
- 각 숫자가 첫 번째 자리에 올 수 있는 경우는 각각 24개
113 ÷ 24 = 4 ... 17
→ 즉, 앞에서 4개의 숫자를 건너뛴 다섯 번째 숫자가 첫 번째 자리에 오게 된다.
- 1 → 스킵
- 2 → 스킵
- 3 → 스킵
- 4 → 스킵
- 5 → 선택
이제 남은 자리(N=4)에 대해 같은 방식으로 K = 17로 계산을 반복하면 된다.
K - 1을 해야하는 이유
컴퓨터는 보통 인덱스를 0부터 시작한다.
하지만 문제에서 K는 1부터 시작하는 1-based index로 주어졌기 때문에,
계산을 0-based로 맞추기 위해 K에 1을 빼주는 것이다.
예를 들어, K = 1일 때는 가장 첫 번째 수열을 의미하고,
0-based로 계산하면 index = 0이 되어야 하므로 K - 1이 필요합니다.
K ÷ (N-1)! 이 N을 넘을 수 있나?
K ÷ (N-1)! 는 리스트에서 뽑을 숫자의 인덱스인데, K는 항상 N! 이하로만 주어진다고 하였으니, 최대 K는 N!이고 0-based로 -1을 하기때문에,
최대 인덱스는
이기 때문에, K / (N-1)! 는 항상 0 이상 N 미만 이기때문에 Out Of Range 오류는 일어나지 않는다.
최종 코드
import java.util.ArrayList;
class Solution {
static ArrayList<Integer> list = new ArrayList<>();
static int[] arr;
public int[] solution(int n, long k) {
k--; // 1-based index를 0-based로 변환
arr = new int[n];
// 1부터 n까지 리스트에 담기
for (int i = 1; i <= n; i++) {
list.add(i);
}
int idx = 0;
while (n > 0) {
long f = factorial(--n); // (n-1)!
int index = (int)(k / f); // 현재 자리에 올 수 있는 숫자의 index 결정
k %= f; // 다음 자리를 위한 k 갱신
arr[idx++] = list.get(index); // 해당 숫자 선택
list.remove(index); // 사용한 숫자 제거
}
return arr;
}
static long factorial(int k) {
long result = 1;
for (int i = 2; i <= k; i++) {
result *= i;
}
return result;
}
}