31. Next Permutation (Array, Two Pointers)

링크 - https://leetcode.com/problems/next-permutation/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

우리는 O(n) 시간 복잡도로 이 문제를 풀 수 있다. 아이디어는 다음과 같다.

1. list의 가장 끝에서부터 왼쪽으로 이동하면서 감소하는 부분(nums[i] < nums[i+1])이 있는지 확인한다.

2. 만약 감소하는 부분이 없다면 전체적으로 list를 reverse한다.

2.1 만약 감소하는 부분을 찾았다면, 그 감소된 부분과, 그 감소된 부분보다 큰 끝쪽에 있는 인덱스를 찾는다. 그리고 그 둘을 swap한뒤, 감소된 부분 오른쪽 부분을 reverse한다.

 

예를 들어, 1-5-8-4-7-6-5-3-1의 다음 permutation은 무엇일까? 위의 알고리즘을 적용해보자.

1. 먼저 오른쪽부터 시작하여 감소하는 부분을 찾는다. 따라서 우리는 4-7에서 처음으로 감소하는 것을 알 수 있으며, 따라서 i를 4의 인덱스인 3으로 설정한다.

2. 다음으로, 오른쪽부터 시작하여 3보다 큰 수를 찾는다. 그것은 5가 되므로, j를 5의 인덱스인 6으로 설정한다.

3. i와 j의 값을 swap한다. 따라서 list는 1-5-7-5-7-6-4-3-1이 된다.

4. 다음으로 i+1부터 list의 오른쪽 끝까지의 부분을 reverse한다. 따라서 list는 1-5-7-5-1-3-5-6-7이된다.

5. 우리는 1-5-8-4-7-6-5-3-1의 다음 permutation은 1-5-7-5-1-3-5-6-7임을 알 수 있다.

Code

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i = len(nums) - 2
        while 0 <= i and nums[i] >= nums[i+1]:
            i -= 1
        if i >= 0:
            j = len(nums) - 1
            while nums[i] >= nums[j]:
                j -= 1
            self.swap(nums, i, j)
        self.reverse(nums, i + 1)

    def reverse(self, nums, start):
        i, j = start, len(nums) - 1
        while i < j:
            self.swap(nums, i, j)
            i += 1
            j -= 1

    def swap(self, nums, i, j):
        temp = nums[i]
        nums[i] = nums[j]
        nums[j] = temp

Complexity

Time Complexity: O(n) 첫번째 while에서 최대 n만큼 동작한다. i >= 0일경우, 다음 while문에서 또 최대 n만큼 동작한다. reverse는 또 O(n)만큼 동작한다. Swap은 O(1)이 걸린다. 따라서 전체적인 time complexity는 O(n)이다. 

Space Complexity: O(1) in-place로 동작하므로 또다른 space가 필요하지 않다.