백준 1722번 순열의 순서 (JAVA)

1722번 순열의 순서 (JAVA)

문제

난이도

• 골드 5

알고리즘 분류

• 구현
• 수학
• 조합론

풀이

최대 20! 연산이 발생할 수 있기 때문에 직접 순열을 구하는 경우 시간 복잡도가 매우 증가한다.

20!을 담기 위해서 타입 선언에 유의한다.

1 ~ N 이 담긴 리스트 생성

소문제 1인 경우, 주어진 K번 째 순열 구하기

계산을 위해 K - 1 (0번째 순열부터)

순열의 개수는 N! 개

앞에 위치할 수를 선택하고 그 뒤에 (N-1)! 만큼의 순열이 올 수 있다.

따라서 K / (N-1)! 을 통해서 앞에 올 숫자가 몇 번째인지를 구할 수 있다.

해당 위치에 올 숫자가 남은 숫자 중 몇 번째 숫자인지 구하고 리스트를 통해서 해당 숫자를 가져온다.

가져온 숫자를 리스트에서 삭제해 중복을 방지한다.

해당 자리에 올 숫자를 구하고 하위 순열에서의 순서를 구해 연산을 반복한다.

소문제 2인 경우, 주어진 순열이 몇 번째인지 구하기

주어진 숫자가 리스트에서 몇 번째 순서인지를 구하고 하위 순열의 개수만큼 곱한다.

예를 들어 3으로 시작하는 경우 1과 2로 시작하는 순열 이후 등장한다. 1과 2로 시작하는 순열은 (N-1)!개의 순열을 각각 가진다.

0번째 순열부터 계산을 시작했기 때문에 마지막에 +1

코드

public class Main {
    public static void main(String[] args) throws Exception {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(in.readLine());

        StringTokenizer st = new StringTokenizer(in.readLine());

        int problem = Integer.parseInt(st.nextToken());

        List<Integer> list = new ArrayList<Integer>();
        for(int i = 1; i <= N;i++) {
            list.add(i);
        }

        if(problem == 1) {
            int[] answer = new int[N];
            long K = Long.parseLong(st.nextToken()) - 1;

            for(int i = 1; i < N; i++) {
                long temp = fact(N-i);

                int cur = (int) (K / temp);

                answer[i-1] = list.get(cur);
                list.remove(cur);

                K -= cur * temp;

            }
            answer[N-1] = list.get(0);

            for(int i = 0; i < N; i++) {
                sb.append(answer[i]).append(" ");
            }
        }

        if(problem == 2) {
            long answer = 0;
            for(int i = 0; i < N; i++) {
                int cur = Integer.parseInt(st.nextToken()); 
                long temp = fact(N-i-1);

                answer += list.indexOf(cur) * temp;
                list.remove(list.indexOf(cur));

            }

            sb.append(answer + 1);
        }

        out.write(sb.toString());
        out.close();
    }

    private static long fact(int n) {
        long temp = 1;
        for(int i = 1; i <= n; i++) {
            temp *= i;
        }
        return temp;
    }
}