[백준/C] 10974 - 모든 순열

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

구현 과정

복잡한 조건 없이 사전순으로 출력만 하면 되는 기본적인 순열 문제이다. 이를 위해 next permutation 알고리즘을 이용한다.

먼저 nums 배열을 선언하고 1부터 n까지의 숫자를 채워준다.

nt *nums = (int *)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++)
        nums[i] = i + 1;

next permutation

pivot = n - 2 부터 시작

1. 처음으로 nums[i] > nums[i + 1]인 i를 찾아야 하므로 그 전까지 i를 계속 감소시킨다. i가 음수가 되면 맨 앞까지 갔는데도 조건을 만족하는 i가 없는 것이므로 마지막 순열에 도달한 것이다. 이 경우는 false를 출력하고 바로 종료한다.

2. next를 감소해가며 pivot의 오른쪽 원소들 중 pivot보다 크면서, 가장 작은 값을 고른다.

3. nums[next], nums[p]를 교환한다.

4. pivot 이후~끝까지의 순열을 뒤집어 저장한다.

5. 모든 과정이 끝나면 true를 리턴하고 종료한다.

bool nextPermutation(int *nums, int n) {
    int p = n - 2;
    while (p >= 0 && nums[p] >= nums[p + 1])
        p--;
    if (p < 0)
        return false;

    int next = n - 1;
    while (nums[next] <= nums[p])
        next--;

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

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

main() 안에서는 nextPermutation이 true 리턴하는 동안만 순열을 출력하게끔 while (valid) 안에서 출력을 실행하고, valid의 값을 매번 업데이트 한다.

bool valid = true;
    while (valid) {
        for (int i = 0; i < n; i++ {
            printf("%d ", arr[i]);
        }
        printf("\n");
        valid = nextPermutation(nums, n);
    }

전체 코드

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

bool nextPermutation(int *nums, int n) {
    int p = n - 2;
    while (p >= 0 && nums[p] >= nums[p + 1])
        p--;
    if (p < 0)
        return false;

    int next = n - 1;
    while (nums[next] <= nums[p])
        next--;

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

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

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

    int *nums = (int *)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++)
        nums[i] = i + 1;

    bool valid = true;
    while (valid) {
        for (int i = 0; i < n; i++) {
            printf("%d ", nums[i]);
        }
        printf("\n");
        valid = nextPermutation(nums, n);
    }
    free(nums);
    return 0;
}