[백준/C] 10972 - 다음 순열

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

생각의 흐름

• n개의 숫자로 만들 수 있는 순열은 총 n!개니까 for문을 1~n!까지 실행하면 되려나?
• for문으로 순열을 계속 검사하다가 (현재 순열 == nums 순열)이면 break하면 되겠다. 근데 같은지 검사하려면 또 for문을 돌아야 하나..?

결국 n!-1번째까지 조합을 검사해야 되는데 어떻게 그걸 검사할지가 관건이다.

next permutation 알고리즘

알고 보니까 다음 순열을 찾는데 적합한 next permutation 알고리즘이 있었다!

과정

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

(1번에서 앞까지 쭉 탐색했는데도 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 p = -1;
    for (int i = n - 2; i >= 0; i--) {
        if (nums[i] < nums[i + 1]) {
            p = i;
            break;
        }
    }

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

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

        int start = p + 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;
}

기억할 것: 두 요소를 배열 뒤에서부터 비교할 때에는 인덱스를 n-2부터 시작해도 된다! 두 개씩 비교하니까 n-1부터 시작하는 게 의미가 없음...