[백준/JAVA] 1722번: 순열의 순서

🔺 문제

1722번: 순열의 순서

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        int N, Q;
        long F[] = new long[21];    // 각 자리별로 만들 수 있는 경우의 수 저장 (팩토리얼 형태)
        int  S[] = new int[21];                 // 순열 담는 배열
        boolean visited[] = new boolean[21];    // 숫자 사용 유무 저장 배열
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        
        st = new StringTokenizer(br.readLine()," ");
        Q = Integer.parseInt(st.nextToken());
        
        // 팩토리얼 초기화 → 각 자리수에서 만들 수 있는 경우의 수
        F[0] = 1;
        for(int i = 1 ; i <= N ; i++) {
            F[i] = F[i - 1] * i;
        }
        
        // 1) 순열 출력 문제
        if(Q == 1) {
            long K = Long.parseLong(st.nextToken());    // 현재 순서
            
            // 팩토리얼 가짓수 치기
            for(int i = 0 ; i < N ; i++) {
                for(int j = 1 ; j <= N ; j++) {
                    if(visited[j]) continue;
                    
                    // 주어진 K에 따라 각 자리에 들어갈 수 있는 수 찾기
                    if(F[N - i - 1] < K) {  // N : 현재 자리
                        K -= F[N - i - 1];
                    }
                    else {  // 해당하는 원소를 찾은 것
                        S[i] = j;   // 현재 자리에 j값 저장
                        visited[j] = true;
                        break;
                    }
                }
            }
            for(int i = 0 ; i < N ; i++) {
                System.out.print(S[i] + " ");
            }
        }
        // 2) 순서 출력 문제
        else {
            for(int i = 0 ; i < N ; i++) {
                S[i] = Integer.parseInt(st.nextToken());    // 순열 배열 저장
            }
            
            long ans = 1;
            
            for(int i = 0 ; i < N ; i++) {
                for(int j = 1 ; j < S[i] ; j++) {
                    // 1부터 해당하는 원소까지 팩토리얼 값 늘려가며 더하기
                    if(visited[j]) continue;
                    ans += F[N - i - 1];
                }
                visited[S[i]] = true;
            }
            System.out.println(ans);
        }
    }
}

✅ 해결 아이디어
✔ 조합 & DP

 

 

- K번째 순열 출력하기

  1) 주어진 값(K)과 현재 자리(N) - 1에서 만들 수 있는 경우의 수 비교

  2) 1에서 K가 더 작아질 때까지 경우의 수를 배수(cnt)로 증가시킴 (순열 순서를 1씩 증가)

  3) K가 더 작아지면, 순열에 값을 저장하고, K를 K - (경우의 수 * (cnt - 1))로 업데이트

  4) 순열이 완성될 때까지 1~3을 반복하고 완료된 순열 출력

 

 

- 입력된 순열의 순서 구하기

  1) N자리 순열의 숫자를 받아 몇 번째 순서의 숫자인지 확인 (현재 숫자 - 자기보다 앞 숫자 중 이미 사용한 숫자)

  2) 해당 순서 * (현재 자리 - 1에석 만들 수 있는 순열의 개수)를 K에 더함

  3) 모든 자릿수에 관해 1~3을 반복한 후 K값 출력

 

 

 

---

🔺 다른 풀이들

- 복습용

백준 1722 순열의 순서 Java

[BOJ] 백준 1722. 순열의 순서

[백준 1722] 순열의 순서

 

 

- 약간 코드가 다름

로그인

 

---

💬 느낀 점

아앗... 머리가 안 돌아가.....

복습을 10번은 해봐야 할 것 같다....

 

1회독	2회독	3회독	4회독	5회독
V	7/3

---

(참고)

[ BOJ ][JAVA][1722] 순열의 순서

 

✔ Do it 알고리즘 코딩테스트 자바편