이전 순열 (10973)

March 02, 2019

이 문제는 순열에 대한 이해가 필요한 문제이다.

순열이란 1부터 N까지로 이루어진 수열을 말하며, 크기는 항상 N이고, 겹치는 수가 존재하지 않는다. N이 5인 경우 $12345$ 와 $54321$ 은 모두 순열이다.

순열은 $N!$ 개가 존재하는데 문제에서 말하는 이전 순열 이란 $N!$ 개의 순열을 사전순으로 나열했을때 주어진 순열의 바로 이전 순서의 순열을 뜻한다.

예를 들어 $1234$ 는 N이 4인 경우 사전순에서 첫 번째의 순열 이므로 이전 순열이 없기 때문에 -1을 반환하며, $1243$ 의 이전 순열은 $1234$ 이다.

prev_permutation

c++에서는 prev_permutation이라는 이전 순열을 만들어 주는 함수를 제공하기 때문에 이 문제를 쉽게 풀 수 있지만, 그렇게 하면 알고리즘을 푸는 의미가 없기 때문에, 직접 만들어 보는게 좋다.

bool prev_permutation(int *a, int n)
{
    int i = n - 1;
    int j = n - 1;

    while (i > 0 && a[i - 1] < a[i]) i--;

    if (i <= 0) return false;

    while (a[i - 1] < a[j]) j--;

    swap(a[i - 1], a[j]);

    while (i < j){
        swap(a[i], a[j]);
        i++;
        j--;
    }

    return true;
}

최종코드

#include <iostream>
#include <vector>

using namespace std;

bool prev_permutation(int *a, int n)
{
    int i = n - 1;
    int j = n - 1;

    while (i > 0 && a[i - 1] < a[i])
    {
        i--;
    }
    if (i <= 0)
        return false;
    while (a[i - 1] < a[j])
    {
        j--;
    }
    swap(a[i - 1], a[j]);
    while (i < j)
    {
        swap(a[i], a[j]);
        i++;
        j--;
    }

    return true;
}

using namespace std;

int main(){
    int n, tmp, i=0;
    cin >> n;
    int a[10000]={0};

    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    if(prev_permutation(a, n)){
        for(int i = 0; i < n; i++){
            cout << a[i] << " ";
        }
    }else{
        cout << "-1";
    }
    return 0;
}