[Gold V] 순열의 순서 - 1722 (JAVA)

문제 요약

1부터 N까지의 수를 임의로 배열한 순열은 총 N! = N×(N-1)×…×2×1 가지가 있다.

임의의 순열은 정렬을 할 수 있다. 예를 들어 N=3인 경우 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}의 순서로 생각할 수 있다. 첫 번째 수가 작은 것이 순서상에서 앞서며, 첫 번째 수가 같으면 두 번째 수가 작은 것이, 두 번째 수도 같으면 세 번째 수가 작은 것이….

N이 주어지면, 아래의 두 소문제 중에 하나를 풀어야 한다. k가 주어지면 k번째 순열을 구하고, 임의의 순열이 주어지면 이 순열이 몇 번째 순열인지를 출력하는 프로그램을 작성하시오.

---

문제 분석

재귀를 사용한 순열 구하기를 사용해서 브루트 포스로 풀면 되겠다 싶었지만, 시간, 메모리 초과를 겪었다.

하다하다 어떻게 해야 할지 모르겠어서 분류 확인했더니 조합론 + 수학이 포함되길래, 이건 순열의 개수를 구하는 공식을 사용해서 풀어야 한다는 생각이 들었다.

---

코드

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

public class Main {
    static int N;
    // 문제조건에서 N은 최대 20까지 가능하다.
    // 20!를 계산하게된다면 int범위를 초과하기 때문에 long으로 선언해준다.
    static long K, cntK;
    // 소문제 번호를 판단하기 위한 변수
    static int problemNo;
    // 소문제 번호가 2번일 경우, 찾아야 하는 순열을 저장하기 위한 배열.
    static int[] targetPermutation;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 두개의 소 문제 중 어떤것인지 확인하는 변수
        problemNo = Integer.parseInt(st.nextToken());
        targetPermutation = new int[N];
        if(problemNo == 1){
            // K가 int범위를 초과할 수 있으므로, long으로 받아준다.
            // 만약 문제가 아래와같이 나온다면, 범위를 초과한다.
            // 20
            // 1 2432902008176640000
            K = Long.parseLong(st.nextToken());
        }
        else if(problemNo == 2){
            int idx = 0;
            while(st.hasMoreTokens()){
                targetPermutation[idx++] = Integer.parseInt(st.nextToken());
            }
            // K와 마찬가지로 int범위를 초과할 수 있으므로, long으로 받아준다.
            cntK = 0;
        }
        // 본 코드
        dfs(0, new int[N], new boolean[N+1]);
    }
    private static boolean dfs(int depth, int[] permutation, boolean[] v){
        if(depth == N){
            // 종료조건에 따라 수행하는 로직이 다르다.
            if(problemNo == 1){
                System.out.println(Arrays.toString(permutation).replaceAll("[\\[\\],]", ""));
                return true;
            }
            else if(problemNo == 2){
                cntK++;
                System.out.println(cntK);
                return true;
            }
        }
        for(int currNum = 1; currNum <= N; currNum++){
            // 이미 방문했던 숫자라면 다음숫자로 넘어간다.
            if(v[currNum] == true){
                continue;
            }
            // problemNo에 따라 다른 로직을 적용해준다.
            // problemNo가 1일경우
            if(problemNo == 1){
                // K를 판별하기 위해선 어떻게해야할까?
                // 현재 depth에서의 순열의 개수는 factorial(N-depth-1)이다.
                // 만약 K가 현재 depth에서의 순열의 개수보다 크다면, 현재 depth에서의 순열에는 K번째 순열이 없다.
                // 따라서 K에서 현재 depth에서의 순열의 개수를 빼준다.
                long temp = factorial(N-depth-1);
                // K가 temp보다 크다면 현재 반복문 다음에 나오는 숫자로 넘어가야한다.
                if(K > temp){
                    // 넘어가기 전에 현재 수에서 만들어질 수 있는 모든 순열의 개수를 K에서 빼준다.
                    K -= temp;
                    continue;
                }
                // 만약 K가 temp보다 작거나 같다면, 현재숫자로 시작하는 순열 안아 K번째 순열이 있다.
                else if(K <= temp){
                    // 현재 수를 현재 depth위치의 permutation에 넣어준다.
                    permutation[depth] = currNum;
                    // 방문처리
                    v[currNum] = true;
                    // 다음 depth로 넘어간 후 K번째 순열을 찾았다면 true를 반환해준다.
                    if(dfs(depth+1, permutation, v) == true){
                        return true;
                    }
                }
            }
            // problemNo가 2일경우
            else if(problemNo == 2){
                // 만약 현재 숫자가 depth번째 숫자와 다르다면 cntK에 factorial(N-depth-1)을 더해준다.
                if(currNum != targetPermutation[depth]){
                    cntK += factorial(N-depth-1);
                    continue;
                }
                // 만약 현재 숫자가 depth번째 숫자와 같다면, 현재 숫자를 permutation에 넣어주고, 방문처리를 해준다.
                else if(currNum == targetPermutation[depth]){
                    permutation[depth] = currNum;
                    v[currNum] = true;
                    if(dfs(depth+1, permutation, v) == true){
                        return true;
                    }
                }
            }
        }

        return false;
    }

    // factorial 함수
    private static long factorial(int n){
        if(n <= 1) return 1;
        return n * factorial(n-1);
    }
}

---

정리

새로 배운 내용

문제를 잘 읽어보고, 못풀겠다면 문제가 요구하는 사항을 순서대로 풀어보자.

• 소문제 2가지를 주며 이 문제의 접근방식을 일정 부분 알려줬다고 생각한다. 소문제 번호가 1번일 때를 우선 해결하고 나니 2번일 경우는 수월하게 해결할 수 있었다.
• int로만 구하다가 답이 안나오길래 뭔가 했더니 int범위 초과였다. 20! 만 해도 엄청 큰 숫자였구나 싶다. 

개선할 점

문제 제대로 읽어보기.

언제나 수학적인 문제에 약하다. 관련 문제를 풀어볼 필요가 있어 보인다.

가끔은 완탐 대신 수학적으로 해결하는 습관도 길러봐야겠다.

더 찾아볼만한 사항

없음

---