[C++] prev_permutation의 동작 원리

C++의 algorithm 헤더에는 prev_permutation이라는 함수가 정의되어 있다. 범위를 인자로 받아서 이전 순열로 바꿔주는 함수이다.

https://en.cppreference.com/w/cpp/algorithm/prev_permutation
자세한 스펙은 위 문서에 소개되어 있다.

이전 순열이란?

https://www.acmicpc.net/problem/10973
백준 10973 - 이전 순열

위 문제는 prev_permutation 함수를 사용하면 아주 쉽게 해결할 수 있다. 하지만 함수 없이 그 원리를 파악해 보며 직접 이전 순열을 구해보기로 했다. 위의 Cpp 공식문서를 참고했다.

먼저, 이전 순열이란 무엇일까? 어떤 순열이 있을 때, 사전순으로 바로 이전에 오는 순열을 뜻한다.

예를 들어 길이 3짜리 모든 순열을 사전순으로 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

이제 거꾸로 한 단계 돌아가면 이전 순열이 된다. 3, 2, 1의 이전 순열은 3, 1, 2가 된다.

1, 2, 3의 경우 이전 순열이 없는데, prev_permutation 함수에서는 다시 마지막 순열(3, 2, 1)을 가리키도록 구현되어 있다. 하지만 위 문제에서는 이전 순열이 없으면 -1을 출력하면 된다. 직접 구현할 때에는 필요에 따라 적절히 예외 처리를 해주면 되겠다.

과정

3, 4, 1, 2라는 배열을 예로 들어 이전 순열을 찾아보자.

1. 오른쪽->왼쪽으로 탐색하며 교환 기준점 k를 찾는다.
2. 교환 대상 m을 찾는다.
3. k-1번째 값과 m번째 값을 교환한다.
4. k번째 이후의 배열을 뒤집는다.

1. pivot 찾기

먼저 배열의 오른쪽부터 왼쪽으로 탐색하면서 오름차순이 처음으로 깨지는 위치를 찾는다. 즉, 처음으로 arr[k-1] > arr[k]이 되는 k를 찾는다. 이 위치를 pivot이라 한다.

• k=3: 2>1은 true이므로 k 감소
• k=2: 1>4은 false이므로 pivot은 2이다.

pivot부터는 오름차순 정렬되어 있다는 것을 알 수 있다(1, 2).

만약 pivot이 0이라면 배열 전체가 오름차순 정렬되어 있다는 뜻이므로, 이전 순열이 존재하지 않는다.

2. 교환 대상 찾기

다음으로 교환 대상 m을 찾는다. 이 값은 이전 순열을 만들기 위해 교환해야 할 적당한 값이다. 적당한 값이란 무엇일까?

k-1번째 값보다 작은 값들 중 가장 오른쪽에 위치한 값을 의미한다. 따라서 m도 마찬가지로 배열의 오른쪽부터 탐색한다.

• m=3: 2는 4보다 작고 가장 오른쪽에 있기 때문에 성립한다. 교환 대상은 3번째 인덱스가 된다.

3. arr[k-1]과 arr[m] 교환

현재 k=2, m=3이다. arr[k-1]과 arr[m] 두 값을 교환하자.

사전 순으로 보았을 때 3, 4, 1, 2에서 3, 2, 1, 4가 되었고, "조금 더 작은" 순열이 되었다. 하지만 바로 이전 순열은 아니다. pivot부터는 여전히 오름차순 정렬되어 있기 때문이다. 3, 2, 1, 4의 다음 순열은 3, 2, 4, 1이다.

따라서 우리는 3, 2로 시작하면서 가장 사전순으로 큰 순열을 만들어주어야 한다.

4. arr[k]이후 배열 뒤집기

pivot 이전까지의 배열은 교환 과정을 거치면서 안정화된 상태이다. 하지만 pivot부터는 사전순으로 더 증가할 가능성이 있기 때문에 내림차순으로 정렬해야 한다.

---

지금까지의 과정을 코드로 옮겨보았다.

소스 코드

#include <iostream>
#include <algorithm>
using namespace std;

int arr[10001];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int N;
    cin>>N;
    for(int i=0; i<N; i++){
        cin>>arr[i];
    }
    
    int k=N-1, m=N-1;
    while(k>0 && arr[k-1]<arr[k]) k--;
    
    if(k==0) {
        // 이전 순열이 없는 경우 적절한 처리
    }
    
    while(arr[k-1]<arr[m]) m--;
    
    swap(arr[k-1], arr[m]);
    
    reverse(arr+k, arr+N);
    
    for(int i=0; i<N; i++){
        cout<<arr[i]<<" ";
    }
}

덧붙이는 말

• pivot을 오름차순이 처음으로 깨지는 두 값 중 작은 값으로 두어도 된다. 현재는 둘 중 큰 값으로 두었기 때문에 교환하는 과정에서 k번째가 아닌 k-1번째와 교환하고 있다. 하지만 이는 구현 차이일 뿐, 전체적인 흐름은 같다.
• 다음 순열을 구하는 next_permutation 함수는 prev_permutation과 반대로 구현하면 된다.
• swap, reverse는 algorithm 헤더에 정의되어 있다.
• 추상적인 생각을 구체적인 단어로 옮기는 것이 정말 어려운 것 같다. 최대한 흐름을 따라가기 쉽게끔 나만의 언어와 그림으로 정리해보았다.