Next Permutation

LeetCode의 Next Permutation 문제를 함께 풀어보도록 하겠습니다.

문제

숫자 배열이 주어졌을 때, 배열 내의 숫자를 재배열하여 다음으로 큰 순열을 만들어내는 로직을 구현하라. 가장 커서 다음으로 큰 순열이 없는 경우, 가장 작은 순열이 다음으로 큰 순열이 된다. 상수 크기의 추가 메모리만을 사용해야 하고 배열 내에서(in place) 재배열을 해야한다.

예시

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

풀이

다음으로 큰 순열로 어떻게 숫자를 재배열할 수 있을지 다음 예제의 통해 생각해보겠습니다.

1, 3, 5, 4, 2

바로 다음으로 큰 순열을 찾아야 하기 때문에 자연스럽게 오른쪽 부터 재배열을 고려해야 합니다. 제일 오른쪽의 두 수인4, 2을 자리를 바꾸면 2, 4이 되어서 오히려 더 작은 순열이 됩니다. 왼쪽으로 한 칸 범위를 늘려 5, 4, 2을 생각해봐도, 이미 이 3개의 만들 수 있는 최대 순열이여서 재배열의 여지가 없습니다. 그 다음으로 3, 5, 4, 2를 생각해보면 4, 2, 3, 5로 재배열하면 다음으로 큰 순열이 됩니다. 따라서 위 예제의 다음으로 큰 순열은 1, 4, 2, 3, 5가 됩니다.

다음으로 큰 순열을 찾기위한 재배열 과정은 다음과 같이 3단계로 정리할 수 있습니다.

최대 순열이 아닐 때 까지 오른쪽부터 왼쪽으로 한 칸씩 사고 범위를 늘려갑니다. (3, 5, 4, 2)
N [나머지] 형태가 주어졌을 때 가장 왼쪽에 있는 N 보다 큰 값을 [나머지] 내에서 찾아서 자리를 바꿔줍니다. (4, 5, 3, 2)
[나머지] 부분에 있는 숫자들을 역순으로 재배열합니다. (4, 2, 3, 5)

위 사고 과정을 그대로 알고리즘으로 구현해보겠습니다.

Python

파이썬은 arr[i], arr[j] = arr[j], arr[i]와 같은 방식으로 쉽게 배열 내 원소 자리 바꾸기를 구현할 수 있습니다.

class Solution:
    def nextPermutation(self, nums):
        i = len(nums) - 1
        while i > 0 and nums[i - 1] >= nums[i]:
            i -= 1

        if i > 0:
            j = i
            while j < len(nums) and nums[i - 1] < nums[j]:
                j += 1
            nums[i - 1], nums[j - 1] = nums[j - 1], nums[i - 1]

        def reverse(start):
            low, high = start, len(nums) - 1
            while low < high:
                nums[low], nums[high] = nums[high], nums[low]
                low, high = low + 1, high - 1

        reverse(i)

Java

자바는 파이썬 같은 문법을 제공하지 않기 때문에 내장 함수로 분리하여 작성하였습니다.

class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 1;
        while (i > 0 && nums[i - 1] >= nums[i])
            i--;

        if (i > 0) {
            int j = i;
            while (j < nums.length && nums[i - 1] < nums[j])
                j++;
            swap(nums, i - 1, j - 1);
        }

        reverse(nums, i);
    }

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

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

복잡도

N을 배열의 길이라고 했을 때, 위 알고리즘은 O(N)의 시간 복잡도와 O(1)의 공간 복잡도를 가집니다. 두 개의 while 반복문을 중첩없이 사용하고 있으며, 변수 외에는 별다른 자료 구조를 사용하고 있지 않기 때문입니다.