[ BOJ ][JAVA][1722] 순열의 순서

www.acmicpc.net/problem/1722

1722번: 순열의 순서

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	8910	2382	1842	30.756%

문제

1부터 N까지의 수를 임의로 배열한 순열은 총 N! = N×(N-1)×…×2×1 가지가 있다.

임의의 순열은 정렬을 할 수 있다. 예를 들어 N=3인 경우 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}의 순서로 생각할 수 있다. 첫 번째 수가 작은 것이 순서상에서 앞서며, 첫 번째 수가 같으면 두 번째 수가 작은 것이, 두 번째 수도 같으면 세 번째 수가 작은 것이….

N이 주어지면, 아래의 두 소문제 중에 하나를 풀어야 한다. k가 주어지면 k번째 순열을 구하고, 임의의 순열이 주어지면 이 순열이 몇 번째 순열인지를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1≤N≤20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1≤k≤N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N까지의 정수가 한 번씩만 나타난다.

출력

k번째 수열을 나타내는 N개의 수를 출력하거나, 몇 번째 수열인지를 출력하면 된다.

예제 입력 1

4
1 3

예제 출력 1

1 3 2 4

예제 입력 2

4
2 1 3 2 4

예제 출력 2

3

코드

/*
    순열의 순서
    조합론 + DP
    N개의 순열의 개수가 N!개 인 점을 생각
*/
import java.io.*;
import java.util.*;
public class p1722 {
    static int n;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        long[] f = new long[21];
        boolean[] visit = new boolean[21];
        Arrays.fill(f, 1);
        for (int i = 1; i <= 20; i++) {
            f[i] = f[i-1] * i;
        }

        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int game = Integer.parseInt(st.nextToken());
        int[] arr = new int[n];
        if (game == 1) {
            long k = Long.parseLong(st.nextToken());

            // 팩토리얼 가짓수 치기
            for (int i = 0; i < n; i++) {
                // 1~N 확인
                for (int j = 1; j <= n; j++) {
                    // 순열에 이미 존재하는 숫자면 넘어간다
                    if (visit[j]) continue;

                    // 팩토리얼 값이 k보다 작으면 k에서 팩토리얼 값을 빼준다
                    if (f[n - i - 1] < k) {
                        k -= f[n - i - 1];
                    } else {
                        // 팩토리얼 값이 k보다 크면 해당하는 원소의 숫자를 찾은 것.
                        // a[i]에 저장하고 순열에 존재하는 숫자를 체크해준다
                        arr[i] =j;
                        visit[j] = true;
                        break;
                    }
                }
            }
            for (int i = 0; i < n; i++) {
                sb.append(arr[i]).append(" ");
            }
        } else {
            for (int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
            long ans = 1;
            for (int i = 0; i < n; i++) {
                for (int j = 1; j < arr[i]; j++) {
                    // 1부터 해당하는 원소까지 팩토리얼 값을 늘려가며 더해준다.
                    if (visit[j]) continue;

                    ans += f[n - i - 1];
                }
                // 순열에 존재하는 숫자는 있다고 표시해준다.
                visit[arr[i]] = true;
            }
            sb.append(ans);
        }

        System.out.println(sb.toString());
    }

}