[10972] 다음 순열

문제: https://www.acmicpc.net/problem/10972

순열이 주어졌을 때 다음 순열을 출력하는 문제이다.

순열의 길이는 최대 10000 이다.

algorithm헤더의 next_permutation(순열 배열의 시작 주소, 끝 주소)를 사용하면

곧 바로 다음 순열을 알 수 있지만

그냥 다음 순열을 계산하는 방법으로 풀었다.

1. 순열을 뒤에서 부터 앞으로 확인하면서 arr[i-1] < arr[i]인 곳을 찾는다.

2. 만약 모든 숫자를 확인했을 때 위의 조건을 만족하지 않으면 마지막 순열이라는 뜻이므로

-1를 출력하고 종료한다.

3. 1의 조건을 만족하는 지점(j)이 있다면 그 j를 기준으로 순열 두 덩이로 나눈다.

4. [j-n]덩어리에서 뒤에서부터 확인하면서  arr[j-1]보다 큰 숫자를 찾아 arr[j-1]과 스왑해준다.

5. 스왑 후 구간 [j~n]을 오름차순으로 정렬해준다.

6. 출력

위 과정을 수행하면 된다.

예시를 예로 들면

arr[1]	arr[2]	arr[3]	arr[4]
6	2	5	1

위와 같은 순열이 있을 때

1. 순열을 뒤에서 부터 앞으로 확인하면서 arr[i-1] < arr[i]인 곳을 찾는다.

arr[1]	arr[2]	arr[3]	arr[4]
6	2	5	1

arr[3] < arr[4]는 false이므로 넘어간다.

arr[1]	arr[2]	arr[3]	arr[4]
6	2	5	1

arr[2] < arr[3]은 조건을 만족한다. index 3을 저장해둔다.

만약 모든 숫자를 비교했을 때 위의 조건을 만족하는 index가 없다면 그 순열을 마지막 순열이라는 뜻이므로

-1을 출력해주면 된다.

3. 1의 조건을 만족하는 지점(j)이 있다면 그 j를 기준으로 순열 두 덩이로 나눈다.

arr[1]	arr[2] (j-1)		arr[3] (j)	arr[4]
6	2		5	1

4. [j-n]덩어리에서 뒤에서부터 확인하면서  arr[j-1]보다 큰 숫자를 찾아 arr[j-1]과 스왑해준다.

arr[1]	arr[2] (j-1)		arr[3] (j)	arr[4]
6	2		5	1

arr[2] < arr[4]은 false이므로 넘어간다.

arr[1]	arr[2] (j-1)		arr[3] (j)	arr[4]
6	2		5	1

arr[2] < arr[3]은 조건을 만족한다. arr[2]와 arr[3]을 스왑해준다.

arr[1]	arr[2] (j-1)		arr[3] (j)	arr[4]
6	5		2	1

5. 스왑 후 구간 [j~n]을 오름차순으로 정렬해준다.

arr[1]	arr[2]		arr[3] (j)	arr[4]
6	5		1	2

6. 출력

arr[1]	arr[2]	arr[3]	arr[4]
6	5	1	2

#include<cstdio>
#include<algorithm>
using namespace std;
int arr[10010];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i<n; i++) {
        scanf("%d", &arr[i]);
    }
 
    int idx = -1;
    for (int i = n - 1; i > 0; i--) {
        if (arr[i - 1] < arr[i]) {
            idx = i;
            break;
        }
    }
 
    if (idx == -1) {
        puts("-1");
        return 0;
    }
 
    for (int i = n - 1; i >= idx; i--) {
        if (arr[idx - 1] < arr[i]) {
            swap(arr[idx - 1], arr[i]);
            break;
        }
    }
 
    sort(arr + idx, arr + n);
 
    for (int i = 0; i<=n - 1; i++) printf("%d ", arr[i]);
 
    return 0;
}