[LeetCode] Next Permutation

https://leetcode.com/problems/next-permutation/

Next Permutation - LeetCode

다음 순열의 값을 찾아내는 문제

순열 규칙을 알게 되었다. 알듯 말듯 아리송하게 풀다가 결국 못 풀었다.

 

풀이 알고리즘은

1. 리스트 오른쪽부터 왼쪽으로 탐색하며 오른쪽 원소와 왼쪽 원소를 비교해서 값이 작아진 경우를 찾는다.

    - 만약 끝까지 찾지 못하였으면 리스트 전체가 역순으로 정렬되어 있으므로 reverse 함(순열 처음 상태로)

2. 해당 위치를 찾았으면 왼쪽 원소가 오른쪽 원소보다 작은 상태이다.

3. 오른쪽부터 왼쪽으로 탐색하면서 값이 계속 커졌었으니까, 현재 왼쪽 원소 값보다 작은 값이 나올 때까지 오른쪽으로 다시 탐색한 후 위치를 변경해주면 오른쪽 배열은 역순으로 정렬되어 있음.

4. 이를 다시 reverse 해주면 다음 순열 위치가 됨.

 

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        # 리스트 오른쪽부터 1까지 탐색
        for i in range(len(nums)-1, 0, -1):
            # i 오른쪽 원소, i-1 왼쪽 원소
            # 오른쪽이 더 크다면 위치 수정할 수 있음
            if nums[i] > nums[i-1]:
                j = i
                # j를 오른쪽으로 옮기면서 i-1보다 작은 원소값이 나올때까지 이동
                while j < n and nums[j] > nums[i - 1]:
                    idx = j
                    j += 1
                # 찾았으니 변경
                nums[idx], nums[i-1] = nums[i-1], nums[idx]
                
                # 역순으로 정렬된 배열의 값을 서로 swap 해주기
                for k in range((n-i)//2):
                    nums[n-k-1], nums[i+k] = nums[i+k], nums[n-k-1]
                break
        else:
            nums.reverse()

시간 복잡도는 O(N)