[1722] 순열의 순서

✔ 순열의 순서

[백준 1722]

문제 분석하기

순열은 순서가 다르면 다른 경우의 수로 인정되므로 N자리로 만들 수 있는 순열의 경우의 수를 구하도록 함

손으로 풀어보기

1. 자릿수에 따른 순열의 경우의 수를 1부터 N자리까지 미리 계산
   • 예) N = 4
     4! 3! 2! 1!이므로 24 6 2 1
2. K가 주어질 때 K번째 순열을 구하도록 함
   • K와 현재 자리(N) - 1에서 만들 수 있는 경우의 수를 비교
   • K가 더 작아질 때까지 경우의 수를 배수(cnt)로 증가시킴
   • K가 더 작아지면 순열에 값을 저장하고 K를 K - (경우의 수 * (cnt - 1))로 업데이트
   • 순열이 완성될 때까지 위를 반복
   • 예) K = 3
     
     • K(3) <= 6 * 1이므로 남은 수(1, 2, 3, 4) 중에서 1번째 수 입력 → 순열의 첫 번째 자리는 1
       K = 3 - (6 * (1 - 1)) = 3이며 K가 더 작아지지 않았으므로 업데이트 X
     • K(3) > 2 * 1
       K(3) <= 2 * 2이므로 남은 수(2, 3, 4) 중에서 2번째 수 입력 → 순열의 두 번째 자리는 3
       K = 3 - (2 * (2 - 1)) = 1이며 K가 더 작아졌으므로 업데이트
     • K(1) <= 1 * 1이므로 남은 수(2, 4) 중에서 1번째 수 입력 → 순열의 세 번째 자리는 2
       K = 1 - (1 * (3 - 1)) = 3이며 K가 더 작아지지 않았으므로 업데이트 X
     • 남아 있는 수(4) 입력 후 순열 출력 → 1 3 2 4
3. 임의의 순열이 주어질 때 이 순열이 몇 번째 순열인지 구하도록 함
   • N자리 순열의 숫자를 받아 몇 번째 순서의 숫자인지 확인 (현재 숫자 - 자기보다 앞 숫자 중 이미 사용한 숫자)
   • 해당 순서 * (현재 자리 - 1에서 만들 수 있는 순열의 개수)를 K에 더함
   • 모든 자릿수에 관해 반복한 후 K값을 출력
   • 예) 임의의 순열 = 1 3 2 4
     • 1은 남아 있는 수(1, 2, 3, 4) 중에서 1번째이므로 K값을 갱신하지 않음 → K = 1
     • 3은 남아 있는 수(2, 3, 4) 중에서 2번째이므로 K = K + (2 * 1) = 3 → K = 3
     • 2는 남아 있는 수(2, 4) 중에서 1번째이므로 K값을 갱신하지 않음  → K = 3
     • 4는 남아 있는 수(4) 중에서 1번째이므로 K값을 갱신하지 않음  → K = 3

슈도코드 작성하기 

F(각 자리별로 만들 수 있는 경우의 수 저장하기 -> 팩토리얼 형태)
S(순열을 담는 배열) visited(숫자 사용 유무 저장 배열) N(순열의 길이)
Q(문제의 종류 -> 1이면 순열 출력하기, 2이면 순서 출력하기)
if(Q == 1) {
    K(몇 번째 순열을 출력할지 입력받기) -> 길이가 N인 순열의 K번째 순서의 순열 출력하기
    for(i -> N만큼 반복하기) {
        cnt = 1
        for(j -> N만큼 반복하기) {
            이미 사용한 숫자는 계산하지 않음
            if(현재 순서가 <= 해당 자리 순열 수 * cnt) {
                현재 순서 = 현재 순서 - (해당 자리 순열 수 * (cnt - 1))
                현재 자리에 j값 저장하기, 숫자 j를 사용 숫자로 체크하기
                반복문 종료
            }
            cnt++
        }
    }
    배열 출력하기
}
else {
    K(순열의 순서 저장 변수)
    S(순열 배열 저장)
    for(i -> N만큼 반복하기) {
        for(j -> S[i]의 수만큼 반복하기) {
            if(방문[j] == false) 
                cnt++;
        }
        K = K + cnt * 현재 자릿수에서 만들 수 있는 경우의 수
        S[i]번째 숫자를 사용 숫자로 변경하기
    }
    K 출력하기
}

코드 구현하기

/**
 * 1722) 순열의_순서
 */
public class D081_1722 {
    // F(각 자리별로 만들 수 있는 경우의 수)
    static long F[] = new long[21];
    // S(순열을 담는 배열)
    static int S[] = new int[21];
    // visited(숫자 사용 유무 저장 배열)
    static boolean visited[] = new boolean[21];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // N(순열의 길이)
        int N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        // 각 자리별로 만들 수 있는 경우의 수를 팩토리얼 형태로 저장하기
        F[0] = 1;
        for (int i = 1; i <= N; i++) {
            F[i] = F[i - 1] * i;
        }
        // Q(문제의 종류)
        int Q = Integer.parseInt(st.nextToken());
        // Q가 1이면 순열 출력하기
        if (Q == 1) {
            // K(몇 번째 순열을 출력할지 입력받기)
            long K = Long.parseLong(st.nextToken());
            for (int i = 1; i <= N; i++) {
                int cnt = 1;
                for (int j = 1; j <= N; j++) {
                    // 이미 사용한 숫자는 계산하지 않음
                    if (visited[j])
                        continue;
                    // 현재 순서가 <= 해당 자리 순열 수 * cnt
                    if (K <= cnt * F[N - i]) {
                        // 현재 순서 = 현재 순서 - (해당 자리 - 1의 순열 수 * (cnt - 1))
                        K -= ((cnt - 1) * F[N - i]);
                        // 순열의 현재 자리에 j값 저장하기
                        S[i] = j;
                        // 숫자 j를 사용 숫자로 체크하기
                        visited[j] = true;
                        // 반복문 종료
                        break;
                    }
                    cnt++;
                }
            }
            // 배열 출력하기
            for (int i = 1; i <= N; i++) {
                System.out.print(S[i] + " ");
            }
        }
        // Q가 2이면 순서 출력하기
        else {
            // K(순열의 순서 저장 변수)
            long K = 1;
            // S(순열 배열 저장)
            for (int i = 1; i <= N; i++) {
                S[i] = Integer.parseInt(st.nextToken());
                long cnt = 0;
                for (int j = 1; j < S[i]; j++) {
                    if (visited[j] == false) {
                        cnt++;
                    }
                }
                // K = K + cnt * 현재 자릿수 - 1에서 만들 수 있는 경우의 수
                K += cnt * F[N - i];
                // S[i]번째 숫자를 사용 숫자로 변경하기
                visited[S[i]] = true;
            }
            // K 출력하기
            System.out.println(K);
        }
    }
}