백준 10974번 모든 순열 :: 마이구미

이 글은 백준 알고리즘 문제 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로 변환하여 계속 이어나갈 수 있게 해주면 된다.

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+1 + " ");
    }
    sb.append("\n");
    while (nextPermutation(array)) {}
 
    System.out.println(sb.toString());
}
 
static boolean nextPermutation(int[] array) {
    // i는 증가하지 않은 가장 긴 접미사 인덱스
    int i = array.length - 1;
    while (i > 0 && 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");
}