[10972,10973,10974번] 다음 순열, 이전 순열, 모든 순열

https://www.acmicpc.net/problem/10972

10972번: 다음 순열

순열이란 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것을 순열(permutation)이라고 합니다. (나무위키 순열 정의 참조)

 

예를 들어 1 2 3 수들을 순열로 나열해보면,

1 2 3 (오름차순)

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1 (내림차순)

이러한 형태가 나타납니다. 여기서 특징은 첫 순열은 항상 오름차순, 마지막 순열을 항상 내림차순 형태를 띄게 됩니다.

또한 부분 순열을 살펴봤을 때에도 부분 순열의 내림차순(마지막 순열) 형태 다음, 그 다음 순열은 오름 차순(시작 순열)의 형태가 나타난다는 것을 확인할 수 있습니다.

 

순열 관련 문제를 풀때는 C++에서는 STL의 algorithm에서 next_permutation(다음 순열), prev_permutation(이전 순열)이 있기 때문에 이를 그대로 사용하면 됩니다. 그러나 Java에서는 이러한 라이브러리가 없기 때문에 이를 구현해주어야 하는데요.

순열 알고리즘의 원리를 이해하기 위해 학습용으로 C++를 이용하여 구현합니다.

 

 

* 다음 순열을 구하는 알고리즘

1. A[i-1] < A[i] 를 만족하는 가장 큰 i를 찾습니다.

i는 순열의 가장 뒤쪽 인덱스부터 작아지는 쪽으로 순차적으로 검사합니다.

예를 들면 현재 순열이 4 2 6 1 5 3 이라는 것이 있습니다. 

 

위 그림처럼 배열 A의 인덱스 i는 0부터 5까지 있습니다.

i가 5일 때부터 해보면, A[4] > A[5] 이므로 조건에 맞지 않으므로 i를 -1 하여 A[3]과 A[4]를 비교해봅니다.

A[3] < A[4]가 성립하므로 우리가 찾기 원하는 가장 큰 i인 4를 구했습니다.

A[i-1] < A[i]를 만족하는 가장 큰 i를 찾는 것입니다.

두 수를 비교하면서 부등호 방향이 > 일 경우 i를 -1씩 줄여가면서 계속 비교하다가 부등호 방향이 < 으로 바뀌는 순간을 찾는 것입니다.

 

즉, i-1번째 인덱스를 기준으로 그 이후 수들은 내림차순 모양새가 나타납니다. i 지점부터 내림차순 모양새를 나타내고 있으므로 내림차순은 마지막 순열입니다. 마지막 순열 다음은 오름차순, 즉 시작 순열이 나와야 하는 것이 순열의 규칙이지요.

 

2. j ≥ i 이고 A[j] > A[i -1] 를 만족하는 가장 큰 j를 찾습니다.

이유는 사전순대로 배열해야하는 순열의 규칙을 따라야 하므로, 지금 찾아야하는 A[j]수는 i -1번째 이후에 있는 수들 중 A[i-1]보다는 커야하면서도 가장 뒤쪽에 위치된 수가 되어야만 합니다.

j를 마지막 인덱스부터 내려가면서 A[j] > A[i-1]를 만족하는 j를 찾습니다. 어차피 j가 끝에서부터 시작하므로 i보다 j가 크거나 같을 수 밖에 없겠지요.

 

현재 i는 4이고, j가 5부터 내려가면서 A[j] > A[i-1]를 비교하는데 바로 A[5] > A[3]이 성립함을 알 수 있습니다. 즉, 그때의 j는 5라는 것을 찾았습니다.

아직 swap을 하진 않았으나 이제 1, 3 두 수를 교환(swap) 해주어야 합니다.

 

3. A[i-1]과 A[j]를 swap합니다.

A[3]과 A[5]를 swap하면 아래와 같이 모습이 됩니다.

 

 

4. A[i]부터 끝까지 순열을 뒤집습니다.

지금 예제는 두개밖에 없어서 서로를 swap하면 되지만, 길이가 길 경우 순서를 뒤집을 때는 제일 처음과 끝을 중간지점에 도달할때까지 계속 swap해주면 됩니다.

 

다음 순열이 완성되었습니다.

 

 

첫번째 문제인 10972번 다음 순열 구하기 문제 코드입니다.

[코드]

#include <iostream>
#include <vector>
using namespace std;
bool next_permutation(int *a, int n) {
    //1.a[i-1] < a[i] 를 만족하는 i찾기
    int i = n - 1;
    while (i > 0 && a[i - 1] >= a[i]) i -= 1;
    //i가 0임에도 1번 조건을 찾을 수 없어 이곳에 도달. 순열이 전부 내림차순 이라는 의미.(= 마지막 순열) 
    if (i <= 0) return false; //마지막 순열은 다음 순열이 없으므로 false를 리턴
    //2.A[j] > A[i -1] 를 만족하는 가장 큰 j 찾기
    int j = n - 1;
    while (a[j] <= a[i - 1]) j -= 1;
    //3.i-1번째 수와 j번째 수를 서로 교환하기
    swap(a[i - 1], a[j]);
    //4.a[i]부터 끝까지 순열을 뒤집기
    j = n - 1;
    while (i < j) {
        swap(a[i], a[j]);
        i += 1; j -= 1; //i부터 증가, j는 끝에서부터 감소
    }
    return true;
}
int main () {
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    if (next_permutation(arr, n)) {
        for (int t : arr) cout << t << ' ';
    } else {
        cout << -1 << '\n';
    }
    return 0;
}

[결과]

4
1 2 3 4 
1 2 4 3

 

 

 

 

 

https://www.acmicpc.net/problem/10973

10973번: 이전 순열

이전 순열은 다음 순열 만들기를 이해하고 나면 쉽습니다.

동일한 알고리즘에 부등호면 변경하면 되니까요.

1, 2번의 while문의 부등호만 반대로 해주면 됩니다.

1번에서의 부등호를 바꾸는 이유는 다음 순열을 찾을 때는 두 수를 비교하는 과정에서 > 방향으로 진행하다가 부등호 방향이 < 으로 바뀌는 순간을 찾았습니다.

이제 이전 순열을 찾을 때는 반대로 두 수를 비교하면서 < 방향으로 진행하다가 > 으로 바뀌는 순간의 i를 찾아야합니다. 

 

2번에서의 부등호를 바꾸는 이유는 다음 수열에서는 A[i-1]보다 크면서 j가 가장 큰 수 A[j]를 찾았습니다.

이전 수열에서는 A[i-1]보다 작으면서 j가 가장 큰 수 A[j]를 찾으면 됩니다.

 

[코드]

#include <iostream>
using namespace std;
bool prev_permutation(int *a, int n) {
    int i = n - 1;
    while (i > 0 && a[i - 1] <= a[i]) i -= 1; //부등호가 반대
    if (i <= 0) return false; // 첫순열
    int j = n - 1;
    while (a[j] >= a[i - 1]) j -= 1; //부등호가 반대
    swap(a[i - 1], a[j]);
    j = n - 1;
    while (i < j) {
        swap (a[i], a[j]);
        i++; j--;
    }
    return true; 
}
int main () {
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    if (prev_permutation(arr, n)) {
        for (int t : arr) cout << t << ' ';
    }else cout << -1;
    cout << '\n';
    return 0;
}

[결과]

5
5 4 3 2 1
5 4 3 1 2

 

 

 

 

 

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

10974번: 모든 순열

1부터 N까지의 수가 있을 때 모든 순열을 출력하기 위해서는 가장 처음의 시작 순열부터 시작해야하므로 오름차순 정렬이 필수입니다. 

그리고 다음 순열 함수를 이용하여 마지막 순열에 도달할 때까지 계속 반복하면서 출력해주면 됩니다.

여기서는 이미 STL의 algorithm 헤더에 구현되어있는 next_permutation 함수를 사용해보도록 합니다.

next_permutation 사용시 인자로 넘겨야 할 것은 정수 배열이 아니라 vector로 배열을 선언해주고 시작과 끝을 넘겨주어야 합니다. 

 

[코드]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main () {
    int n;
    cin >> n;
    vector<int> arr(n);
    //배열에 이미 순서대로 정렬되어 들어간 상태
    for (int i = 0; i < n; i++) {
        arr[i] = i + 1;
    }
    do {
        for (int t : arr) cout << t << ' ';
        cout << '\n';
    }while (next_permutation(arr.begin(), arr.end()));
    return 0;
}

[결과]

3
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1