[JAVA] 백준 1722 - 순열의 순서

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

순열의 길이 N과 소문제 번호와 관련 데이터가 주어졌을 때 정답을 출력하는 문제이다.

1번 소문제는 숫자 K가 추가로 주어지며 길이 N으로 만들 수 있는 사전 순 K 번째 순열을 출력하는 문제이고,

2번 소문제는 순열이 주어졌을 때 이 순열이 몇번째 순열인지를 출력하는 문제이다.

첫번째 문제는 먼저 한 숫자가 고정되었을 때 순열의 개수를 구하는데에서 시작했는데, 이는 (N-1)!이다.

길이 N의 순열의 개수가 N! = N X N -1 X ... X 2 X 1일 때 N을 1로 치환한 값이기 때문이다.

따라서 N이 4라면 개수는 4!=24이고 첫번째 자리에 들어올 수 있는 1~4의 숫자들이 3!=6 개씩 경우의 수를 차지한다.

그러므로 K가 주어졌을 때 1부터 N까지 순회하며 i번째 자릿수에 대해 K를 (n-i)!로 나눈 값 num을 구하고 

1~N 중 아직 등장하지 않은 num번째 숫자를 뽑았다.이때 K를 (n-i)!로 나눈 나머지가 0일 경우 num에서 1을 빼주었다.

 

두번째 문제는 이 과정을 거꾸로 한 느낌인데, 순열에서 뽑은 숫자를 읽고 뽑은 숫자 보다 작은 숫자 중 아직 등장하지 않은 숫자의 개수 count를 세어서 (N-i)!을 곱한뒤 이 값을 더하면서 N번째 자릿수까지 순회했다.

 

dp[target-1]을 dp[target]-1로 적어서 한번 틀렸다.

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

public class Main {
    static long[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = par(br.readLine());
        dp = new long[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        long f = getFact(n);
        long[] arr = Arrays.stream(br.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
        if (arr[0] == 1) {
            long acheive = arr[1];
            int target = n;
            boolean[] visited = new boolean[n+1];
            for (int i =0; i <n; i++) {
                long complete = 0;
                long first = acheive/dp[target-1];
                long rest = acheive%dp[target-1];
                if(rest==0) first--;
                int number = getIndex(visited,(int)first+1);
                visited[number] = true;
                complete+=first*dp[target-1];
                target--;
                acheive-=complete;
                System.out.print(number);
                if(i!=n-1) System.out.print(" ");
            }
        } else {
            int target = n;
            long count = 0;
            boolean[] visited = new boolean[n+1];
            for (int i = 1; i <=n; i++) {
                long t = arr[i];
                visited[(int)t] = true;
                long calc = getCount(visited, t) * dp[target-1];
                count += calc;
                target--;
            }
            count++;
            System.out.println(count);
        }
    }
    static int getIndex(boolean[] visited, int idx){
        int count = 0;
        for (int i = 1; i < visited.length; i++) {
            if(visited[i]) continue;
            count++;
            if(count==idx) return i;
        }
        return 0;
    }

    static int getCount(boolean[] visited, long target){
        int count = 0;
        for (int i = 1; i <=target ; i++) {
            if(!visited[i]) count++;
        }
        return count;
    }
    static long getFact(long n) {
        if(dp[(int)n]!=0) return dp[(int)n];
        for (int i = 2; i <=n; i++) {
            dp[i] = dp[i-1]*i;
        }
        return dp[(int)n];
    }

    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}