본문 바로가기

Programming/BOJ

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;
}





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)




참고



태그