next_permutation 구현하기

모든 순열을 다 구해야 할까?

PS를 하다 보면 순열을 다뤄야 하는 경우가 많습니다. 가장 흔하게 접하는 방식은 DFS를 활용한 백트래킹으로 $N$개의 원소로 만들 수 있는 모든 순열을 구하는 것입니다.

만약 문제의 요구사항이 “가능한 모든 순열을 출력하라”라면 DFS 방식은 훌륭한 정답입니다. 하지만 “현재 주어진 순열의 바로 다음 순열을 구하라”는 요구사항이라면 이야기가 달라집니다.

예를 들어, [1, 2, 3, 4]라는 수열이 있고, 현재 상태가 [1, 4, 3, 2]라고 가정해봅시다. DFS 방식을 사용한다면 우리는 처음 [1, 2, 3, 4]부터 시작해서 재귀를 돌며 순서를 바꾸다가, 현재 상태인 [1, 4, 3, 2]와 일치하는지 확인하고, 그제야 비로소 그 다음 순열을 반환해야 합니다.

이 방식의 치명적인 단점은 현재 순열이 전체 순열 중 몇 번째인지 알기 위해 불필요한 앞선 연산을 수행해야 한다는 점입니다. 최악의 경우 시간 복잡도는 $O(N!)$에 육박하게 됩니다.

C++을 사용하는 경우 <algorithm> 헤더에서 제공하는 std::next_permutation 함수를 사용하면 내부적으로 최적화된 알고리즘을 통해 다음 순열을 $O(N)$의 시간 복잡도로 구해줍니다. 하지만 Java와 같은 언어에서는 표준 라이브러리에서 이를 직접적으로 지원하지 않기 때문에, 이 알고리즘의 원리를 이해하고 직접 구현할 수 있어야 합니다.

이 글에서는 next_permutation이 어떤 원리로 동작하여 다음 순열을 찾아내는지 알아보고, 이를 Java로 구현해보겠습니다.

본론

1. 알고리즘의 목표

우리가 구현하고자 하는 next_permutation의 목표를 엄밀하게 정의하면 다음과 같습니다.

$K$번째 순열 $P_k = {p_1, p_2, \dots, p_n}$ 이 주어졌을 때, $P_k$보다 사전순으로 더 큰 임의의 순열 $P_i$ 중에서 사전순으로 가장 빠른(작은) 순열을 구한다.

쉽게 말해, 현재 순열보다 “바로 다음으로 큰” 순열을 찾는 것입니다.

2. 동작 원리

이 알고리즘은 크게 4단계로 나눌 수 있습니다. 예시로 [1, 4, 3, 2]의 다음 순열을 찾아보겠습니다.

Step 0: 사전순의 정의와 전략

사전순(Lexicographical Order)의 정의에 따르면, 앞쪽에 위치한 원소($a_i$)가 뒤쪽에 위치한 원소($a_{i+1}$)보다 순서 결정에 더 큰 영향력을 가집니다. 따라서 “바로 다음” 순열을 구하기 위해서는, 최대한 뒤쪽에 있는(영향력이 작은) 원소를 교체하여 변화의 폭을 최소화해야 합니다. 만약 어떤 구간이 이미 내림차순으로 정렬되어 있다면, 그 구간 안에서는 더 이상 사전순으로 뒤에 오는 순열을 만들 수 없습니다(이미 해당 조합으로 만들 수 있는 가장 큰 수이기 때문입니다). 따라서 우리는 이 내림차순이 깨지는 지점(Boundary)을 찾아야 합니다.

Step 1: 오름차순이 깨지는 지점 찾기 (Boundary 설정)

뒤에서부터 앞으로 탐색하면서, 인접한 두 수 $A[i-1]$과 $A[i]$를 비교합니다. $A[i-1] < A[i]$를 만족하는 가장 큰 $i$를 찾습니다. 이때 $i-1$이 바로 교환이 일어날 위치(pivot)가 됩니다. $i$부터 끝까지는 내림차순으로 정렬된 상태입니다.

• 예시: [1, 4, 3, 2]
  • 2 < 3? (X)
  • 3 < 4? (X)
  • 4 < 1? (X) -> 1 < 4 (O)!
  • 여기서 $i=1$ (값 4), $i-1=0$ (값 1) 입니다. pivot은 0번 인덱스(값 1)입니다.

Step 2: 교환할 값 찾기 (최소한의 변화)

이제 $A[i-1]$을 더 큰 수로 바꿔야 순열의 순서가 뒤로 넘어갑니다. 하지만 “바로 다음” 순열이 되려면, $A[i-1]$보다 크면서 가장 작은 수와 교체해야 영향력의 차분을 최소화할 수 있습니다. $i$부터 끝까지는 내림차순이므로, 뒤에서부터 탐색했을 때 $A[i-1]$보다 처음으로 큰 값이 바로 그 대상($A[j]$)이 됩니다.

• 예시: [1, 4, 3, 2] (pivot 값: 1)
  • 2 > 1? (O) -> 찾았다! $j=3$ (값 2).
  • (뒤에서부터 찾으므로 가장 먼저 발견된 2가 1보다 큰 수 중 가장 작은 수임이 보장됩니다.)

Step 3: Swap

$A[i-1]$과 $A[j]$를 교환합니다.

Step 4: 뒷부분 정렬 (Reverse)

$A[i-1]$과 $A[j]$를 교환한 후에도, $i$부터 끝까지의 뒷부분은 여전히 내림차순이 유지됩니다. 우리는 앞자리를 1에서 2로 바꿈으로써 이미 더 큰 순열을 만들었습니다. 이제 뒷부분을 사전순으로 가장 빠르게(오름차순) 만들어야 “바로 다음” 순열이 완성됩니다. 뒷부분이 내림차순임이 보장되므로, 단순히 뒤집기(Reverse)만 하면 오름차순 정렬이 완료됩니다.

왜 Swap 후에도 내림차순이 유지될까요?

$i$부터 끝까지는 내림차순이므로 $A[j-1] \ge A[j] \ge A[j+1]$ 인 상태입니다. 여기서 $A[j]$는 $A[i-1]$보다 큰 값 중 가장 뒤에 있는(가장 작은) 값입니다. 즉, 다음 조건들이 성립합니다.

1. $A[j] > A[i-1]$ (Step 2의 조건)
2. $A[j+1] \le A[i-1]$ ($A[j]$가 조건을 만족하는 마지막 원소였으므로, 그 다음 원소는 $A[i-1]$보다 작거나 같아야 함)

이제 $A[j]$ 자리에 $A[i-1]$이 들어갑니다.

• 왼쪽 관계: $A[j-1] \ge A[j] > A[i-1]$ 이므로, $A[j-1] > A[i-1]$ (내림차순 유지)
• 오른쪽 관계: $A[i-1] \ge A[j+1]$ (위 2번 조건에 의해 내림차순 유지)

따라서 Swap 후에도 해당 구간은 내림차순 구조가 깨지지 않습니다.

3. Java 구현

위의 로직을 Java 코드로 구현하면 다음과 같습니다.

import java.util.Arrays;

public class NextPermutation {

    public static boolean nextPermutation(int[] arr) {
        int i = arr.length - 1;

        // Step 1: A[i-1] < A[i]를 만족하는 가장 큰 i를 찾는다.
        while (i > 0 && arr[i - 1] >= arr[i]) {
            i--;
        }

        // 마지막 순열인 경우 (전체가 내림차순)
        if (i <= 0) {
            return false;
        }

        // Step 2: A[i-1]보다 큰 값 중 가장 뒤에 있는 A[j]를 찾는다.
        int j = arr.length - 1;
        while (arr[j] <= arr[i - 1]) {
            j--;
        }

        // Step 3: A[i-1]과 A[j]를 교환한다.
        swap(arr, i - 1, j);

        // Step 4: i부터 끝까지 뒤집는다.
        reverse(arr, i);

        return true;
    }

    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    private static void reverse(int[] arr, int start) {
        int end = arr.length - 1;
        while (start < end) {
            swap(arr, start, end);
            start++;
            end--;
        }
    }
}

결론: 언제 사용해야 할까?

지금까지 next_permutation의 동작 원리와 구현 방법을 알아보았습니다. 이 알고리즘의 가장 큰 장점은 현재 상태에서 다음 상태로 넘어가는 비용이 $O(N)$이라는 점입니다.

DFS를 이용한 완전 탐색은 모든 경우의 수를 구해야 하거나, 순열의 크기($N$)가 매우 작을 때 유용합니다. 하지만 다음과 같은 상황에서는 next_permutation이 훨씬 강력한 도구가 됩니다.

1. 특정 순열 이후의 순열만 필요할 때: 전체를 탐색할 필요 없이 현재 상태에서 바로 다음 상태를 $O(N)$만에 구할 수 있습니다.
2. 메모리 제한이 엄격할 때: 재귀 호출 스택을 사용하지 않고 반복문과 스왑만으로 동작하므로 메모리 효율이 뛰어납니다.
3. 사전순으로 $K$번째 순열을 찾아야 할 때: 수학적 규칙을 이용할 수도 있지만, $N$이 적당히 작다면 next_permutation을 $K$번 반복하여 직관적으로 구할 수도 있습니다.

Java에서는 C++처럼 표준 라이브러리로 제공되지 않아 직접 구현해야 하는 번거로움이 있지만, 그 원리를 이해하고 있다면 언제든 필요할 때 응용할 수 있습니다.