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

문제

https://www.acmicpc.net/problem/1722

1722번: 순열의 순서

 

설명

1부터 N까지의 수를 임의로 배열한 순열은 총 N! = N × (N-1) × … × 2 ×1 가지가 있다.
둘째 줄의 첫 번째 수가 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다.
k가 주어지면 k번째 순열을 구하고, 임의의 순열이 주어지면 이 순열이 몇 번째 순열인지를 구해야 한다.

먼저 순열을 구하는 함수인 perm을 재귀함수를 이용해 만든다. 

long perm(int num) {
    if (num == 0)
        return 1;
    return num * perm(--num);
}

둘째 줄의 첫 번째 수가 1인 경우부터 보면, 방문 여부를 확인하기 위한 visited[] 배열을 이용해 방문하지 않았다면 target과 perm(N - i - 1)을 비교한다.

perm(N - i - 1) 이 의미하는 것은 현재 자리 뒤로 만들 수 있는 순열의 가짓수이다.

i = 0일 경우, 현재 자리는 N개의 자리 중 첫번째 자리를 의미하고 그 뒤 (N - 1)개의 자리에 올 수 있는 순열의 가짓수를 구할 수 있다. 

target이 경계보다 클 경우, target에서 경계값을 뺀 후 다음 방문하지 않은 수를 찾는다.

작을 경우에는 미리 만들어놓은 sb에 현재 j를 추가하고 방문 처리를 한다.

long target = Long.parseLong(st.nextToken());
StringBuilder sb = new StringBuilder();

for (int i = 0; i < N; i++) {
    for (int j = 1; j <= N; j++) {
        if (!visited[j]) {
            // target이 경계보다 클 경우
            if (target > perm(N - i - 1)) {
                target -= perm(N - i - 1);
            }
            // target이 경계보다 작을 경우
            else {
                sb.append(j);
                sb.append(" ");
                visited[j] = true;
                break;
            }
        }
    }
}

sb.deleteCharAt(sb.length() - 1);
System.out.println(sb);

둘째 줄의 첫 번째 수가 2인 경우에는, 순열을 하나 입력받고 방문 여부를 확인하기 위한 visited[] 배열을 이용해 방문하지 않은 곳을 찾는다.

입력한 순열의 첫번째 자리부터 나아가면서 result에 방문하지 않은 곳의 perm(N - i - 1) 값을 더하면서 입력한 순열의 순서를 찾는다.

num = new int[N];
for (int i = 0; i < N; i++) {
    num[i] = Integer.parseInt(st.nextToken());
}

long result = 0;
for (int i = 0; i < N; i++) {
    for (int j = 1; j < num[i]; j++) {
        if (!visited[j])
            result += perm(N - i - 1);
    }

    visited[num[i]] = true;
}

System.out.println(result + 1);

 

전체 코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static int N, flag;
    static int[] num;
    static boolean[] visited;

    static long perm(int num) {
        if (num == 0)
            return 1;
        return num * perm(--num);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        visited = new boolean[N + 1];

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

        flag = Integer.parseInt(st.nextToken());
        if (flag == 1) {
            long target = Long.parseLong(st.nextToken());
            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (!visited[j]) {
                        // target이 경계보다 클 경우
                        if (target > perm(N - i - 1)) {
                            target -= perm(N - i - 1);
                        }
                        // target이 경계보다 작을 경우
                        else {
                            sb.append(j);
                            sb.append(" ");
                            visited[j] = true;
                            break;
                        }
                    }
                }
            }

            sb.deleteCharAt(sb.length() - 1);
            System.out.println(sb);
        }
        else {
            num = new int[N];
            for (int i = 0; i < N; i++) {
                num[i] = Integer.parseInt(st.nextToken());
            }

            long result = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 1; j < num[i]; j++) {
                    if (!visited[j])
                        result += perm(N - i - 1);
                }

                visited[num[i]] = true;
            }

            System.out.println(result + 1);
        }
    }
}