백준/1722 순열의 순서

작성일 | In

< 문제 분석 및 풀이 방법 >

Backjoon :: 순열의 순서 문제는 직접 구하지 않고 수학적인 연산이 필요하다.

  • 범위가 최대 20!이기 때문에 구하려고 들면 시간초과가 날 수 밖에 없다.
  • 아이디어는 factorial 값을 저장해둔 배열을 하나 만들고 모듈러 연산을 한다.
  • 만약 [3, 2, 4, 1] 배열이 있다고 했을 때 첫 번째가 4라면 [1, x, x, x], [2, x, x, x] 의 경우는 진행한 것으로 간주해 factorial[3] * 2 = 12 를 더한다.
  • 이후 두 번째 숫자가 2라면 [3, 1, x, x]의 경우의 수는 전부 진행한 것으로 간주해 factorial[2] * 1 을 더한다.
  • k를 입력받을 때 1을 빼주는데 이유는 k 번째 다음 순열을 출력하기 때문이다.
  • factorial 배열, 입력받는 k 변수는 long 형으로 선언해야 한다. 범위를 초과하기 때문!

< 소스 코드 >

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.io.*;
import java.util.*;

public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
    public static int n;
    public static long[] factorial;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        int[] num = new int[n];
        factorial = new long[n + 1];                //Factorial값 미리 구해서 저장
        boolean[] isUsed = new boolean[n + 1];      //i번째 숫자 사용 여부
        getFactorial();

        stk = new StringTokenizer(br.readLine());
        int type = Integer.parseInt(stk.nextToken());
        if (type == 1) {
            long k = Long.parseLong(stk.nextToken()) - 1;
            for (int i = n; i > 0; i--) {
                long mod = k / factorial[i - 1] + 1;    //i번째에서 몇 번째 숫자를 선택할 지 구한다
                k %= factorial[i - 1];
                long cnt = 0;       //mod 번째 숫자를 찾기 위한 변수
                int idx = 0;        //앞에서부터 해당 숫자를 확인할 때 사용하는 변수
                while (cnt != mod) {
                    idx++;
                    if (!isUsed[idx]) cnt++;
                }
                isUsed[idx] = true;
                sb.append(idx + " ");
            }
        } else {
            long ans = 0;
            for (int i = 0; i < n; i++) {
                num[i] = Integer.parseInt(stk.nextToken());
                long cnt = 0;       //움직이는 횟수
                int idx = 0;        //idx 숫자를 사용했는지 확인하는 변수
                while (num[i] != idx) {
                    idx++;
                    if (!isUsed[idx]) cnt++;
                }
                isUsed[idx] = true;
                ans += (cnt - 1) * factorial[n - i - 1];
            }
            sb.append(ans + 1);
        }
        System.out.println(sb);
    }

    public static void getFactorial() {     //factorial값 구하는 함수
        factorial[0] = 1;
        factorial[1] = 1;
        for (int i = 2; i <= n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }
    }
}