[C++] 백준 - 10973 : 이전 순열

문제 링크

10973번: 이전 순열

 

풀이 ) 구현

  이 전에 포스팅한 다음 순열을 반대로 적용시키면 된다.

 

1. 먼저 배열의 뒤부터 두 개씩 비교하여 앞의 숫자가 더 큰 경우가 있는지 확인한다.

  1 2 3 4 5 같이 오름차순으로 정렬된 숫자의 경우 모두 앞의 숫자가 작기 때문에 다음 순열이 존재하지 않아 -1을 출력하고 종료한다.

 

2. 앞부분의 숫자가 더 큰 부분을 경계로 해서 뒷부분의 숫자 중 앞의 경계 값보다 작은 값을 찾는다.

  3 4 1 2 5의 경우 3 4 | 1 2 5로 나뉘고 뒷부분의 숫자를 뒤부터 앞의 경계 값인 4와 비교한다.

  4 < 5 -> 4 > 2 : break

 

3. 위에서의 두 값 4와 2의 자리를 바꿔준 다음 뒷부분을 내림차순으로 정렬해준다.

  3 4 | 1 2 5 -> 3 2 | 1 4 5 -> 3 2 | 5 4 1

 

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

int arr[10001];

bool dec(int a, int b){
    return a>b;
}

int main(void)
{
    int n, i;
    scanf("%d", &n);

    for(i = 0; i < n; ++i)
        scanf("%d", arr+i);

    if(n == 1){
        printf("-1\n");
        return 0;
    }
// 1 start
    for(i = n-1; i > 0; --i)
        if(arr[i-1] > arr[i])
            break;
    if(i == 0)
        printf("-1\n");
// 1 end
// 2 start
    else{
        int j = n-1;
        while(arr[i-1] < arr[j])
            j--;
// 2 end
// 3 start
        swap(arr[i-1], arr[j]);

        sort(arr+i, arr+n, dec);
// 3 end
        for(int k = 0; k < n; ++k)
            printf("%d ", arr[k]);
    }
    return 0;
}

 

※ next_permutation()와 같이 algorithm 라이브러리의 prev_permutation()을 통해서 쉽게 구할 수 있다.