[백준 10972번] 다음 순열

풀이

---

STL을 사용하면 매우 간단하게 구현할 수 있다.

STL을 사용하지 않고 풀어보기 위해서는 먼저 규칙성을 찾아야한다.

N=3

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

N=4

1 2 3 4

1 2 4 3

1 3 2 4

1 3 4 2

1 4 2 3

1 4 3 2

2 1 3 4

2 1 4 3

2 3 1 4 

2 3 4 1

2 4 1 3

2 4 3 1

3 1 2 4

3 1 4 2

3 2 1 4

3 2 4 1

3 4 1 2

3 4 2 1

4 1 2 3

4 1 3 2

4 2 1 3

4 2 3 1

4 3 1 2

4 3 2 1

N=3일경우에는 규칙을 비교할 수 있는 데이터양이 적어서 N=4인 경우 규칙성을 찾아보기가 조금 쉽다..

규칙

1. 오른쪽에서 왼쪽으로 이동하면서 n과 n-1을 비교한다.

2. n-1 < n인경우를 찾는다. 찾은 인덱스를 기준으로 왼쪽 영역과 오른쪽 영역을 나눌 수 있다.

ex) 12543  --> 12 543

     123645987  --> 123645 987 

3. 해당 인덱스에 있는 숫자를 가지고 오른쪽 영역에서 오른쪽부터 왼쪽영역으로 움직이면서 크기를 비교한다.

4. 크다면 자리를 바꾼다.

5. 오른쪽영역의 숫자를 오름차순으로 정렬해준다.

글보다 숫자로 표기하면 더 이해하기 쉽다.

입력 : 326154

--> 3261 54  (영역 나누기)

--> 3261 54  (크기 비교하기)

--> 3264 51  (자리 바꾸기)

--> 3264 15  (오름차순 정렬)

출력 : 326415

코드

---

#include <iostream>
using namespace std;
 
int n, num[10002];
 
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> num[i];
    }
    int tmp_add=n;
    int tmp = num[n];
    for (int i = n; i >= 2; i--) {
        if (num[i - 1] < num[i]) {
            tmp_add = i-1;
            tmp = num[i-1];
            break;
        }
    }
    if (tmp_add == n) {
        cout << -1;
        return 0;
    }
    for (int i = n; i > tmp_add; i--) {
        if (tmp < num[i]) {
            int ch = num[tmp_add];
            num[tmp_add] = num[i];
            num[i] = ch;
            break;
        }
    }
    for (int i = tmp_add+1; i <= n-1; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (num[i] > num[j]) {
                int tmp = num[i];
                num[i] = num[j];
                num[j] = tmp;
            }
        }
    }
 
    for (int i = 1; i <= n; i++) {
        cout << num[i] << " ";
    }
    return 0;
}

참고 자료

---

http://wordaligned.org/articles/next-permutation