BOJ 10972 · 다음 순열

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

순열 알고리즘은 C++ STL에 구현되어 있다. algorithm 라이브러리에 있는 next_permutation 함수를 이용하면 된다. next_permutation은 배열(또는 벡터)의 범위를 인자로 받고, 다음 순열이 존재하면 true를 없으면 false를 반환한다.

next_permutation을 구현하는 방법은 아래와 같다. 배열 또는 벡터의 이름이 a라고 가정하자.

• 인덱스 i가 0보다 크고, a[i-1] >= a[i] 를 만족하면, 인덱스 i를 1씩 반복적으로 감소시킨다.
• 반복문을 벗어난 후, 인덱스 i가 0이면, 다음 순열이 존재하지 않으므로 false를 반환한다.
• a[i-1] >= a[j] 를 만족하면, 인덱스 j를 1씩 반복적으로 감소시킨다.
• a[i-1]의 값과 a[j]의 값을 맞바꾼다.
• a[i]부터 순열의 마지막까지 순서를 뒤집는다.
• 마지막으로 true를 반환한다. 다음 순열은 배열 a에 저장되어 있다.

---

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 (next_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 next_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 (next_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 next_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 next_permutation(a) is True:
    for i in a:
        print(i, end=' ')
    print()
else:
    print(-1)

---

참고

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