[백준/C] 10972 - 이전 순열

https://www.acmicpc.net/problem/10973

previous permutation 알고리즘

과정

1. 뒤에서부터 시작해 탐색하다가 처음으로 i > i+1인 i를 pivot으로 지정
2. pivot의 오른쪽 원소들 중 pivot보다 작으면서, 가장 큰 값을 찾는다.
3. 그 원소 ⇄ pivot 교환 (이제 pivot이 새로운 원소를 가리키게 된다.)
4. pivot의 오른쪽 부분을 뒤집어 정렬하면, 그게 다음 순열이 된다.

(앞에서 뒤까지 쭉 탐색했는데도 i > i+1인 i가 존재하지 않으면 주어진 순열이 최소 순열인 것이므로 이전 순열이 존재하지 않음 ➡︎ -1 출력하고 끝냄)

전체 코드

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n;
    scanf("%d", &n);

    int *nums = (int *)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++)
        scanf("%d", &nums[i]);

    int pivot = -1;
    for (int i = n - 2; i >= 0; i--) {
        if (nums[i] > nums[i + 1]) {
            pivot = i;
            break;
        }
    }

    if (pivot == -1) 
        printf("-1\n");
    else {
        int next = -1;
        for (int i = n - 1; i > pivot; i--) {
            if (nums[i] < nums[pivot]) {
                next = i;
                break;
            }
        }

        int temp = nums[next];
        nums[next] = nums[pivot];
        nums[pivot] = temp;

        int start = pivot + 1;
        int end = n - 1;
        while (start < end) {
            temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }

        for (int i = 0; i < n; i++)
            printf("%d ", nums[i]);
        printf("\n");
    }

    free(nums);
    return 0;
}