• 백준 10974번 모든 순열 :: 마이구미
    알고리즘 풀이/수학 2016. 10. 25. 22:08
    반응형

     글은 백준 알고리즘 문제 10974번 "모든 순열" 를 풀이한다.

    perm 알고리즘을 통해 문제를 해결할 수 있다.

    참고 링크 - https://www.nayuki.io/page/next-lexicographical-permutation-algorithm

    10974번 - https://www.acmicpc.net/problem/10974


    N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

    첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.


    이번 문제는 테스트 케이스를 보면 1 <= N <= 8 인 것을 볼 수 있다.

    뭐 어떻게 풀어도 시간제약이나 메모리 제약에 상관없이 풀 수 있다는 걸 알 수 있다.

    즉, 아무것도 고려하지 않고 답만 뽑아내면 된다.


    C++로 푼다면 STL에 포함되어 있는 next_permutation 함수를 통해 쉽고 풀 수 있다.


    while (next_permutation(p, p + n))


    안타깝게 Java는 위와 같은 함수를 제공하지 않는다.

    구현하는 방법은 다음과 같다.


    일단 4가지 순서를 먼저 기억하자.


    1. Find largest index i such that array[i − 1] < array[i].
      (If no such i exists, then this is already the last permutation.)

    2. Find largest index j such that j ≥ i and array[j] > array[i − 1].

    3. Swap array[j] and array[i − 1].

    4. Reverse the suffix starting at array[i].


    각각의 번호를 자세히 알아보자.
    1번의 경우 증가하지 않는 가장 긴 접미사의 헤드 인덱스를 구하는 것이다.
    예를 들면 다음과 같다.

    1234이 있을 때 구하고자하는 인덱스는 3이다.

    1243이 있을 때 구하고자하는 인덱스는 2이다.

    1324이 있을 때 구하고자하는 인덱스는 3이다.

    1342이 있을 때 구하고자하는 인덱스는 2이다.

    1423이 있을 때 구하고자하는 인덱스는 3이다. => 14 보다 123의 길이가 더 길다

    1432이 있을 때 구하고자하는 인덱스는 1이다.


    2번으로 가기 전 1번에서 구한 인덱스는 피벗으로 활용할 것이다.

    arr[인덱스-1] 이라는 피벗이 만들어졌다.


    이제 2번으로 가보자.

    그리고 피벗을 하나 더 만들 것이다.

    위의 만든 피벗과 새로운 피벗을 서로 바꾸어서 다음 순열로 만들기 위해서이다.


    1번에서 만든 인덱스는 증가하지 않는 접미사를 기준으로 만들어졌다.

    이 말은 그 인덱스 요소는 접미사 중 가장 큰 요소가 될 것이고, 뒤의 요소들은 차례로 작은 순서로 이루어져있다.


    이렇게 2번에서 만들어진 새로운 피벗과 1번의 피벗을 활용하여 3번 순서가 되는 것이다.

    3번의 스왑을 통해 다음 순열을 만들 수 있게 되는 것이다.


    또한 문제에서는 사전순을 바라기 때문에 4번 과정이 필요한 것이다.

    예를 들어, 1432 다음에는 2431이 나오게 된다.

    이와 같은 경우가 발생함으로 4번과정을 통해 2134로 변환하여 계속 이어나갈 수 있게 해주면 된다.



    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    static int n;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
     
        n = Integer.parseInt(br.readLine());
        int[] array = new int[n];
     
        for(int i=0;i<n;i++) {
            array[i] = i+1;
            sb.append(i++ " ");
        }
        sb.append("\n");
        while (nextPermutation(array)) {}
     
        System.out.println(sb.toString());
    }
     
    static boolean nextPermutation(int[] array) {
        // i는 증가하지 않은 가장 긴 접미사 인덱스
        int i = array.length - 1;
        while (i > && array[i - 1>= array[i]) {
            i--;            
        }
     
        // 마지막 변경이 되었을 때 4321일 경우 i는 위의 접미사 인덱스를 구하는 과정에서 -1이 됨.
        if (i <= 0)
            return false;
     
        // array[i - 1] 요소를 피벗으로 정함.
        // 위의 피벗과 스왑할 위의 피벗을 초과한 가장 큰 오른쪽 요소를 찾음.
        int j = array.length - 1;
        while (array[j] <= array[i - 1]) {
            j--;            
        }
        // array[j] <= array[i - 1] 조건인 이유는.
        // array[j]는  array[i - 1]보다 항상 커야하기 때문이다. 
        // => 사전 순으로 모든 경우의 수를 들려야하기 때문.
        // array[i - 1] 와 array[j]를 이용하여 새로운 피벗 구함.
        // array[j] 요소가 새로운 피벗이 된다.
        // Assertion: j >= i
     
        // 피벗 2개는 서로 스왑에 이용하기 위해 사용됨.
        // 새로운 피벗을 이용하여 스왑.
        int temp = array[i - 1];
        array[i - 1= array[j];
        array[j] = temp;
     
        // 위의 과정이 일어나더라도 사전순으로 되지 않음.
        // 접미사 인덱스를 활용하여 반대로 만들어준다.
        j = array.length - 1;
        while (i < j) {
            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            i++;
            j--;
        }
     
        print(array);
        return true;
    }
     
    public static void print(int[] array) {
        for(int i=0;i<n;i++) {
            sb.append(array[i] + " ");
        }
        sb.append("\n");
    }
    cs


    반응형

    댓글 0

Designed by Tistory.