링크
https://www.acmicpc.net/problem/1722
입력 예제
4
1 3출력 예제
1 3 2 4풀이
특정 순서의 순열을 찾거나, 특정 순열의 순서를 찾아야 한다. 이때 모든 순열에 대해서 탐색하는 경우는 최악의 경우 N이 20이기 때문에 시간 초과가 발생한다. 만 되어도 거의 5억이기 때문에 은 엄청 큰 수이다. 이때 시간 복잡도는 이다.
따라서 k 번째 순열을 찾는 경우는 각 자리의 수를 결정해나가는 방식으로 하면 시간 복잡도는 각 자리에 대해 연산이 필요하므로 이 된다. 그리고 주어진 순열의 순서는 각 자리에 대해 가능한 순열의 개수를 계산해가며 순서를 계산한다. 이 방식 또한 시간 복잡도는 가 된다.
우선 k번째 순열을 찾는 경우부터 생각해보면, N=4일 때 3번째 순열을 구한다고 할 때, 첫 번째 자리의 수부터 결정해야 한다. 이때 0 based index이기 때문에 대신 2번째로 계산한다.
- 1 _ _ _
- 나머지 자리에 가능한 순열의 수 3! = 6
- 2 < 6이기 때문에 1로 결정
- 1 2 _ _
- 순열의 수 2! = 2
- 3 > 2이기 때문에 다음 수로 넘긴다.
- 2 -= 2
- 1 3 _ _
- 순열의 수 2! = 2
- 0 < 2이기 때문에 3으로 결정
- 1 3 2 _
- 순열의 수 1
- 0 < 1이기 때문에 2로 결정
- 1 3 2 4
- 순열의 수 없는 경우 1
- 0 < 1이기 때문에 4로 결정
코드로 구현하면 다음과 같다.
private static void findPermutation(int depth) {
if (depth == 0) { //남은 자릿수가 없을 때
StringBuilder sb = new StringBuilder();
for (Integer num : result) {
sb.append(num).append(" ");
}
System.out.println(sb);
return;
}
long blockSize = factorial[depth - 1]; //나머지 자리에 가능한 순열의 경우의 수
for (int i = 1; i <= N; i++) {
if (!visited[i]) {
if (k < blockSize) { //현재 자리에 i를 추가
result.add(i);
visited[i] = true;
findPermutation(depth - 1);
} else { //현재 블록을 건너뜀
k -= blockSize;
}
}
}
}이번엔 순열 1324의 순서를 구해본다.
- 1 _ _ _
- 1보다 작은 수는 없으니 스킵
- 1 3 _ _
- 3보다 작은, 방문하지 않은 수는 2
- 나머지 자리의 순열의 경우의 수 2
- 1 3 2 _
- 2보다 작은 수는 없으니 스킵
- 1 3 2 4
- 4보다 작은 수는 없으니 스킵
따라서 순열의 경우의 수의 총합은 2가 되며 순서는 2번째가 된다.
코드로 구현하면 다음과 같다.
//주어진 순열이 몇 번째 순열인지 찾기
private static void findOrder(int depth) {
if (depth == N) { //마지막 자리까지 탐색한 경우
return;
}
int cur = permutation[depth]; //현재 자리의 숫자
long count = 0;
//현재 자리의 숫자보다 작은 숫자들을 탐색
for (int i = 1; i < cur; i++) {
if (!visited[i]) {
count += factorial[N - depth - 1]; //나머지 자리로 만들어지는 순열의 수
}
}
visited[cur] = true; //방문 처리
order += count;
findOrder(depth + 1);
}전체 코드
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
/*
백준 / 순열의 순서 / 골드5
https://www.acmicpc.net/problem/1722
*/
public class Main {
private static long[] factorial;
private static boolean[] visited;
private static int N;
private static long k, order;
private static List<Integer> result = new ArrayList<>();
private static int[] permutation;
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("wda067/io/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
visited = new boolean[N + 1];
//팩토리얼 배열 초기화
factorial = new long[N + 1];
factorial[0] = 1;
for (int i = 1; i <= N; i++) {
factorial[i] = factorial[i - 1] * i;
}
StringTokenizer st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
if (x == 1) { //k번째 순열 찾기
k = Long.parseLong(st.nextToken()) - 1;
findPermutation(N);
} else { //주어진 순열의 순서 찾기
permutation = new int[N];
for (int i = 0; i < N; i++) {
permutation[i] = Integer.parseInt(st.nextToken());
}
findOrder(0);
System.out.println(order + 1);
}
}
//k번째 순열 찾기
private static void findPermutation(int depth) {
if (depth == 0) { //남은 자릿수가 없을 때
StringBuilder sb = new StringBuilder();
for (Integer num : result) {
sb.append(num).append(" ");
}
System.out.println(sb);
return;
}
long blockSize = factorial[depth - 1]; //나머지 자리에 가능한 순열의 경우의 수
for (int i = 1; i <= N; i++) {
if (!visited[i]) {
if (k < blockSize) { //현재 자리에 i를 추가
result.add(i);
visited[i] = true;
findPermutation(depth - 1);
} else { //현재 블록을 건너뜀
k -= blockSize;
}
}
}
}
//주어진 순열이 몇 번째 순열인지 찾기
private static void findOrder(int depth) {
if (depth == N) { //마지막 자리까지 탐색한 경우
return;
}
int cur = permutation[depth]; //현재 자리의 숫자
long count = 0;
//현재 자리의 숫자보다 작은 숫자들을 탐색
for (int i = 1; i < cur; i++) {
if (!visited[i]) {
count += factorial[N - depth - 1]; //나머지 자리로 만들어지는 순열의 수
}
}
visited[cur] = true; //방문 처리
order += count;
findOrder(depth + 1);
}
}
백엔드