[수학] 백준 1722번 순열의 순서 - JAVA

 

 

오늘의 공포 문제

순열의 순서이다...

 

---

1. 출처

---

 

 

1722번: 순열의 순서

 

 

 

8트 끝에 맞춘 눈물나는 문제...ㅋ

 

 

---

2. 설계

---

 

 

 

 

노란색으로 형광색칠한 곳이 1번이면 순열을 보여주고, 2번이면 순서를 보여주면 된다. 그나마 원리를 알면 구현하기 쉬웠던 2번 먼저 설계를 하겠다.

 

---

 

 

2번 유형 설계

 

1) 4가지 수로 뽑아낼 수 있는 순열은 몇 개 일까?

 

1 2 3 4

1 2 4 3

.

.

. 

 

등등 4자리이기 때문에 4!일 것이다. 이거에 집중해서 2번 유형을 설계해보자!

 

 

4가지 숫자로 1 3 2 4가 몇 번째 순열인지 구하려면 어떻게 해야할까?

 

 

1-1) 만약 첫 번째 자리에 1번을 고른다면 어떨까?

1번 이전에 오는 경우의 수는 없을 것이다.

이게 무슨소리냐? 만약 첫 번째 자리에 2번을 고른다고 생각해보자.

 

 

 

1-2) 만약 첫 번째 자리에 2번을 고른다면 어떨까?

2 _ _ _

2번이 오면 첫 번째 자리에 1번이 오는 경우의 수를 모두 센 다음에 2번이 올 수 있다.

첫 번째 자리에 1번이 오는 경우의 수 (1 _ _ _ => 3!)

이말은 즉, 지금 나의 수 대비 올 수 있는 작은 수의 경우를 다 따져줘야 한다는 것이다.

 

 

 

1-1) 만약 첫 번째 자리에 3번을 고른다면 어떨까?

첫 번째 자리에 3번이 오면 1 _ _ _ 과 2 _ _ _ 으로 올 수 있는 모든 경우를 다 따져준 다음에 3번이 올 수 있는 것이다.

그렇기 때문에 2X3! = 12가지 다음 13번째 부터 3 _ _ _ 이 될 수 있는 것이다.

 

 

 

 

2) 2번 유형 예제를 진행해보자!

 

 

2-1) 1번에 1이 왔을 때 경우의 수 계산

1 이전에 올 수 있는 수는 없다. 따라서 이전 경우의 수는 없다.

 

현재까지 올 수 있는 이전 경우의 수 0

 

 

2-2) 2번에 3이 왔을 때 경우의 수 계산

3 이전에 올 수 있는 수는 아직 방문하지 않은 2가 있다.

따라서 1 2 _ _ => 2!이라는 경우의 수를 고려한다.

 

현재까지 올 수 있는 이전 경우의 수 2

 

 

2-3) 3번에 2가 왔을 때 경우의 수 계산

2 이전에 올 수 있는 수는 없다. 따라서 이전 경우의 수는 없다.

 

현재까지 올 수 있는 이전 경우의 수 2

 

 

2-4) 4번에 4가 왔을 때 경우의 수 계산

4 이전에 올 수 있는 수는 없다. 따라서 이전 경우의 수는 없다.

 

 

현재까지 올 수 있는 이전 경우의 수 2

 

 

 

따라서 이전의 올 수 있는 경우의 수가 모두 온 다음에 나오는 수이므로 정답은 2(이전에 나올 수 있는 경우의 수라는 뜻) + 1(다음에 오는 수라는 뜻) = 3이다.

 

---

 

1번 유형 설계

 

자... 이제 마의 1번 유형을 설계해보자!

2번 유형과 크게 다르지 않다.

 

3) 1번 유형 예제를 진행해보자!

 

 

 

이 문제를 해석하면 1 2 3 4로 순열을 만들되 3번째로 오는 순열을 달라는 것이다.

 

 

3-1-1) 1번에 4이 왔을 때 경우의 수 계산

만약 4 _ _ _ 이라면 어떨까?

1 _ _ _ , 2 _ _ _, 3 _ _ _ 의 경우의 수를 모두 고려한 다음에 나올 수 있는 게 4 _ _ _ 이다.

그래서 3 x 3! = 6x3 = 18가지가 이전에 있다는 의미다. 우리가 구하려고 하는 3번째 순열 보다 멀리 동 떨어졌다.

 

 

3-1-2) 1번에 3이 왔을 때 경우의 수 계산

만약 3 _ _ _ 이라면 어떨까?

1 _ _ _ , 2 _ _ _의 경우의 수를 모두 고려한 다음에 나올 수 있는 게 3 _ _ _ 이다.

그래서 2 x 3! = 6x2 = 12가지가 이전에 있다는 의미다. 우리가 구하려고 하는 3번째 순열 보다 멀리 동 떨어졌다.

 

 

3-1-3) 1번에 2가 왔을 때 경우의 수 계산

만약 2 _ _ _ 이라면 어떨까?

1 _ _ _ 의 경우의 수를 모두 고려한 다음에 나올 수 있는 게 2 _ _ _ 이다.

그래서 1 x 3! = 6x1 = 6가지가 이전에 있다는 의미다. 우리가 구하려고 하는 3번째 순열 보다 멀리 동 떨어졌다.

 

 

3-1-4) 1번에 1이 왔을 때 경우의 수 계산

만약 1 _ _ _ 이라면 어떨까?

1 앞에는 아무것도 고려할 게 없다. 때문에 이전 경우의 수는 0이다.

우리가 구하려고 하는 3번째 순열의 앞에 있으므로 1을 채택한다.

 

 

.

.

.

 

지금 내가 하나의 자릿수를 구하려고 했던 방식처럼 가장 큰 수에서 점점 내려오며 내가 구하려고 하는 경우의 수보다 작을 때 그 수를 채택하고 다음 자릿수를 구하면 된다.

 

다음 자릿수로 넘어가기 전에 (3번째 순열 - 내가 계산한 이전 경우의 수)를 계산해줘야 한다.

 

 

위 내용 설명이 좀 더러운데... 찬찬히 이해가 되었다면 아래 코드가 수월하게 읽힐 것이다!

 

 

---

3. 전체 코드

---

 

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

public class Main {

    static long[] factorial;
    static int N;
    static boolean[] sel;
    
     public static void main(String[] args) throws IOException, NumberFormatException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        //팩토리얼 구하기
        factorial = new long[N+1]; //1!부터 시작
        Factorial(N);

        sel = new boolean[N+1]; //1부터 시작

        
        String commands = br.readLine();
        StringTokenizer st = new StringTokenizer(commands, " ");
        
        int command = Integer.parseInt(st.nextToken());
        
        if(command==1){ //순열구하기 ex) 1 3 2 4
            long order = Long.parseLong(st.nextToken());
            
            numberInfo[] numbers = new numberInfo[N+1];

            for(int i=1;i<=N;i++){//몇번째 자리?
                for(int j=N;j>=1;j--){//무슨 숫자? 뒤에서 부터 살펴주다가 처음 알맞은 숫자 pick!

                    if(sel[j]) continue;

                    int prev_num=prev_num_check(j);
                    long prevCount = factorial[N-i]*prev_num;

                    if(prevCount<order){//해당 숫자는 들어갈 수 있음

                        numbers[i] = new numberInfo(j, order-prevCount);
                        sel[j] = true;
                        order = order-prevCount;
                        break;

                    }
                }
            }

            for(int i=1;i<=N;i++){
                System.out.printf(numbers[i].num+" ");
            }

        }else if(command==2){//이 순열은 몇 번째?

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

            long prevCount = 0; //가짓수
            for(int i=0;i<N;i++){ //정답 이전에 나올 수 있는 모든 가짓수를 체크
                int prev_num=prev_num_check(inputNumbers[i]);
                prevCount+=factorial[(N-(i+1))]*prev_num;
                sel[inputNumbers[i]] = true;
            }

            // 정답 이전에 나올 수 있는 모든 가짓수를 체크했으므로 그 다음 순서(+1)가 정답
            System.out.println(prevCount+1);

        }

    }

    public static void Factorial(int N){

        factorial[0] = 1;
        factorial[1] = 1;

        for(int i = 2; i <= N; i++){
            factorial[i] = factorial[i-1] * i;
        }

    }

    public static int prev_num_check(int target){ //타겟 수 앞에 수가 몇 개가 있는지?
        int count = 0;
        for(int i=1;i<target;i++){
            if(!sel[i]) count++;
        }

        return count;
    }

    public static class numberInfo{
        int num;
        long remainNum;

        public numberInfo(int num, long remainNum){
            this.num = num;
            this.remainNum = remainNum;
        }
    }
    
}

 

 

지금보니 numberInfo 클래스는 딱히 필요 없는 것 같다.

여러 시도를 하면서 이 점을 고려하지 못한 것 같다...

numbers에는 int만 넣어도 될 듯!