문제
1부터 N까지의 수로 이루어진 순열에서, (1) K번째 순열을 구하거나, (2) 주어진 순열이 몇 번째인지 구하라.
입력
첫째 줄에 N (1 ≤ N ≤ 20), 둘째 줄에 명령(1 또는 2)과 K 또는 순열이 주어진다.
출력
명령 1이면 K번째 순열을, 명령 2이면 순열의 순서를 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 1 3 | 1 2 3 5 4 |
풀이
팩토리얼 수 체계를 이용하여 순열의 순서와 K번째 순열을 변환한다.
- 0!부터 N!까지 팩토리얼을 미리 계산한다
- 명령 1 (K번째 순열 찾기): 각 자리에서 (N-i-1)!보다 K가 크면 다음 수로, 아니면 해당 수를 선택. 사용한 수는 visited로 표시
- 명령 2 (순열의 순서 찾기): 각 자리에서 현재 수보다 작고 미사용인 수의 개수 * (N-i-1)!을 K에 더한다
- N이 최대 20이므로 팩토리얼이 long 범위를 넘지 않는다
핵심 아이디어: N개의 원소 중 i번째 위치에 올 수 있는 경우의 수는 (N-i-1)!이므로, 이를 기준으로 K를 분해하면 각 자리의 값을 결정할 수 있다.
코드
import java.io.*;
import java.util.*;
public class Day373BOJ1722순열의순서 { // gg
static int N, cmd;
static long k;
static int[] arr;
static long[] facto;
static boolean[] visited;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
cmd = Integer.parseInt(st.nextToken());
arr = new int[N];
facto = new long[N + 1];
visited = new boolean[N + 1];
facto[0] = 1;
for (int i = 1; i < N + 1; i++)
facto[i] = facto[i - 1] * i;
if (cmd == 1) {
k = Long.parseLong(st.nextToken());
for (int i = 0; i < N; i++) {
for (int j = 1; j < N + 1; j++) {
if (visited[j])
continue;
if (facto[N - i - 1] < k)
k -= facto[N - i - 1];
else {
arr[i] = j;
visited[j] = true;
break;
}
}
}
System.out.println(print(arr));
} else {
for (int i = 0; i < N; i++)
arr[i] = Integer.parseInt(st.nextToken());
k = 1L;
for (int i = 0; i < N; i++) {
for (int j = 1; j < arr[i]; j++)
if (!visited[j])
k += facto[N - i - 1];
visited[arr[i]] = true;
}
System.out.println(k);
}
br.close();
}
private static String print(int[] arr) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < arr.length; i++)
sb.append(arr[i] + " ");
return sb.toString();
}
}복잡도
- 시간: O(N²)
- 공간: O(N)