[ 백준 9742 ] 순열

1. 문제

9742번: 순열

 

2. 풀이

본 문제는 크게 두 가지 방법으로 풀이가 가능하다. 다만, 두 가지 경우 모두 사전 작업이 한 가지 필요한데 이는 바로 주어진 쿼리가 수행 가능한 쿼리인지 먼저 확인하는 것이다. 여기서 수행 가능한 쿼리란 어떤 것을 의미하는 것일까?

 

문제에서 주어진 순열의 인덱스가 과연 존재하는 인덱스인지 검증이 필요하다는 것이다. 서로 다른 문자로 이루어진 문자열로 순열을 만드는 방법은 (순열의 길이)! 이다. 즉, 입력 받은 순열의 길이 팩토리얼 값을 가지고 가능한 인덱스인지 판단할 수 있다. 다만, 현재 문제에서 문자열의 길이는 10 이하이므로, 쿼리들을 입력 받기 이전에 1 ~ 10까지의 팩토리얼을 미리 연산해두면 보다 용이하게 문제를 풀이할 수 있다.

 

다음으로는 두 가지 방법에 대해 차례대로 알아보자!

 

1.1) 백트래킹

백트래킹을 통해 순열을 만드는 것은 기본적인 테크닉으로, 순차적으로 순열 요소들을 만들면서 문제에서 주어진 인덱스에 도달할 경우 탐색을 중단하는 방식을 취하면 된다. 순열을 만드는 방법은 아래 문제의 코드를 통해서 익혀보자.

2023.02.14 - [Algorithm/문제풀이] - [ 백준 14534번 ] String Permutation

 

소스코드

public class Main {

    static int[] fact = new int[11];

    static char[] arr, chars;
    static boolean[] visit;
    static int n, cnt;
    static String ans;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        calcFactorial();

        String line = "";
        while ((line = br.readLine()) != null && !line.equals("")) {
            bw.write(String.format("%s = ", line));

            StringTokenizer st = new StringTokenizer(line);
            arr = st.nextToken().toCharArray();
            n = Integer.parseInt(st.nextToken());

            cnt = 0;
            visit = new boolean[arr.length];
            chars = new char[arr.length];

            if (n > fact[arr.length]) {
                bw.write("No permutation\n");
            } else {
                bw.write(solveWithBacktracking() + "\n");
            }
        }

        bw.close();
        br.close();
    }

    static void calcFactorial() {
        fact[0] = 1;
        for (int i = 1; i <= 10; i++) {
            fact[i] = fact[i - 1] * i;
        }
    }

    static String solveWithBacktracking() {
        cnt = 0;
        visit = new boolean[arr.length];
        chars = new char[arr.length];

        backtracking(0);

        return ans;
    }

    static void backtracking(int len) {
        if (len == arr.length) {
            cnt++;
            if (cnt == n) {
                ans = new String(chars);
                return;
            }
        }

        for (int i = 0; i < arr.length; i++) {
            if (visit[i]) continue;
            visit[i] = true;
            chars[len] = arr[i];
            backtracking(len + 1);
            visit[i] = false;
        }
    }
}

1.2) 수학적 접근

첫 번째 방법은 어떻게 보면 무식하게 풀기(Brute Force) 방식이라고 볼 수 있다. 모든 순열을 만들면서 인덱스에 도달했을 때, 순회를 중단하기 때문이다. 하지만 정해진 순서에 따라서 만들어지는 순열에는 한 가지 규칙이 숨어있다.

 

예를 들어 길이 4의 abcd 라는 입력을 가지고 순열을 만든다고 가정해보자. 향후 모듈러 연산을 위해 인덱스는 0부터 시작한다. 만들 수 있는 순열을 나열해보면 아래와 같다.

뭔가 규칙이 보이지 않는가.

문자열 길이 순열의 첫 번째 요소를 지정하는 방식은 전체 문자열의 길이인 4에서 1을 뺀 3!과 일치한다. 이유는 너무나도 간단하다. 네 개의 요소 중 하나가 정해졌으므로 남은 세 가지 요소로 만들 수 있는 경우의 수는 3!이기 때문이다.

 

그렇다면 이 단순하고 명확한 규칙을 이용해서 어떻게 주어진 index에 맞는 순열을 찾아낼 수 있을까?

 

정답은 나눗셈과 나머지 연산이다. 예를 들어 abcd 문자열로 만들 수 있는 22번째 요소를 탐색한다고 가정해보자. 첫 번째 섹션은 (4 - 1)! = 6 개로 나뉠 수 있으므로, 22 / 6 = 3 을 통해 3 번째 구역에 속해있음을 알 수 있다. 즉 첫 번째 요소는 abcd[3] == d가 된다.

 

나머지 세 자리는 총 6가지의 경우의 수를 가지므로, 22 % 6 = 4로써 집합 내에서 4번째에 위치하고 있음을 알 수 있다. 그럼 정확한 위치를 파악했으므로, 다시 4를 (3 - 1)! = 2로 나누어 준다면 2번째 구역에 속해있음을 알 수 있고, abcd[2] == c를 선택할 수 있게 되는 것이다.

 

다만 이 과정에서, 다른 요소가 이미 선택되었을 수 있으므로 선택되지 않은 요소들 중에서 index를 찾는 것만 주의해주면 된다.

 

원리는 파악했으니 이것을 재귀로 구현하면 풀 수 있다🤗

 

소스코드

public class Main {

    static int[] fact = new int[11];
    static char[] chars;
    static boolean[] visit;
    static String ans;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        calcFactorial();

        String line = "";
        while ((line = br.readLine()) != null && !line.equals("")) {
            bw.write(String.format("%s = ", line));

            StringTokenizer st = new StringTokenizer(line);
            chars = st.nextToken().toCharArray();
            int targetIdx = Integer.parseInt(st.nextToken());

            visit = new boolean[chars.length];
            if (targetIdx > fact[chars.length]) {
                bw.write("No permutation\n");
            } else {
                // 모듈러 연산을 위해 입력 받은 index에서 1을 빼준다.
                solve(targetIdx - 1, visit.length, "");
                bw.write(ans + "\n");
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }

    static void calcFactorial() {
        fact[0] = 1;
        for (int i = 1; i <= 10; i++) {
            fact[i] = fact[i - 1] * i;
        }
    }

    static void solve(int idx, int len, String str) {
        if (len < 1) {
            ans = str;
            return;
        }

        int i = idx / fact[len - 1];
        
        // 이미 선택된 요소를 배제하고 선택되지 않은 요소들의 index 카운트
        int cnt = 0;
        for (int t = 0; t < visit.length; t++) {
            if (visit[t]) continue;

            if (i == cnt) {
                visit[t] = true;
                str += chars[t];
                break;
            }

            cnt++;
        }
        
        // 모듈러 연산을 통해 다음 구역 지정해주기
        solve(idx % fact[len - 1], len - 1, str);
    }
}

 

---

 

 

[Silver 3] 9742번 순열 by kwanik-kor · Pull Request #24 · kwanik-kor/BOJ