[골드5, 순열] 백준 1722 - 순열의 순서 (자바)

Think

1. 주어진 N의 범위를 보고, 일반적인 순열 알고리즘으로는 시간초과가 나겠다는 생각을 했다.

2. 문제풀이 아이디어가 떠오르지 않아 https://nanyoungkim.tistory.com/233를 참고했다.

3. 순열의 경우의 수 = 팩토리얼인 사실을 활용한 풀이방식이다. 범위만큼의 팩토리얼을 미리 초기화하고, k에 순열 경우의수를 빼면서 값을 찾거나, 순열 값 이전까지 탐색하면서 k의 값을 구하는 방식이 되게 인상깊었다.

 

 

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class test {
    static int N, problemNumber, inputs[];
    static long k, factorial[], answer;
    static boolean isSelected[];
    static LinkedList<Integer> answerList = new LinkedList<>();
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        init();

    }

    private static void init() throws IOException {
        N = Integer.parseInt(br.readLine());

        isSelected = new boolean[N+1];

        factorial = new long[21];
        factorial[0] = 1;
        for (int i = 1; i < 21; i++) {
            factorial[i] = factorial[i - 1] * i;
        }

        st = new StringTokenizer(br.readLine());
        problemNumber = Integer.parseInt(st.nextToken());

        if (problemNumber == 1) {
            k = Long.parseLong(st.nextToken());

            for (int i = 0; i < N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (isSelected[j]) continue;
                    if (k - factorial[N - 1 - i] > 0) {
                        k -= factorial[N - 1 - i];
                    } else {
                        isSelected[j] = true;
                        answerList.add(j);
                        break;
                    }
                }
            }

            for (int i = 0; i < answerList.size(); i++) {
                sb.append(answerList.get(i)).append(' ');
            }
            System.out.print(sb);

        } else {
            inputs = new int[N];

            int index = 0;
            while (st.hasMoreTokens()) {
                inputs[index++] = Integer.parseInt(st.nextToken());
            }

            for (int i = 0; i < N; i++) {
                for (int j = 1; j < inputs[i]; j++) {
                    if(isSelected[j]) continue;

                    answer += factorial[N - 1 - i];
                }
                isSelected[inputs[i]] = true;
            }

            System.out.print(answer + 1l);
        }
    }
}