BOJ 10973 · 이전 순열

알고리즘 분류 : 브루트 포스  

C++ STL의 algorithm에 있는 prev_permutation 함수를 사용하면 된다.

prev_permutation 구현 방법은 next_permutation과 똑같이 구현할 수 있으며, 순서만 바꾸면 된다.

next_permutation 구현 방법은 다음 글을 참조.

---

C++ 소스코드

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

int main() {
    int n;
    scanf("%d", &n);
    int a[n];
    for (int i=0; i<n; i++) scanf("%d", &a[i]);
    if (prev_permutation(a, a+n)) {
        for (int i=0; i<n; i++) printf("%d ", a[i]);
        printf("\n");
    } else printf("-1\n");
    return 0;
}

#include <cstdio>

void swap(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

bool prev_permutation(int *a, int *b) {
    int n = int(b-a)-1;
    int i = n; // Find index i
    while (i > 0 && a[i-1] <= a[i]) i--;
    if (i == 0) return false;
    int j = n; // Find index j
    while (a[i-1] <= a[j]) j--;
    swap(&a[i-1], &a[j]); // Swap
    j = n;
    while (i < j) {       // Reverse
        swap(&a[i], &a[j]);
        i++, j--;
    }
    return true;
}

int main() {
    int n;
    scanf("%d", &n);
    int a[n];
    for (int i=0; i<n; i++) scanf("%d", &a[i]);
    if (prev_permutation(a, a+n)) {
        for (int i=0; i<n; i++) printf("%d ", a[i]);
        printf("\n");
    } else printf("-1\n");
    return 0;
}

---

Python 3 소스코드

def prev_permutation(a):
    n = len(a) - 1
    i = n
    while i > 0 and a[i-1] <= a[i]:
        i -= 1
    if i == 0:
        return False
    j = n
    while a[i-1] <= a[j]:
        j -= 1
    a[i-1], a[j] = a[j], a[i-1]
    j = n
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1
    return True

n = int(input())
a = list(map(int, input().split()))

if prev_permutation(a) is True:
    for i in a:
        print(i, end=' ')
    print()
else:
    print(-1)

---

참고

• 백준 온라인 저지 : BOJ 10973
• 다음 순열
• 위키피디아 : 순열