[leetcode] 31. Next Permutation

문제 설명

링크
다음 사전 순서 배열 찾기

접근 1 - 역순회

• 끝에서 부터 탐색하며 내림차순이 어긋나는 부분 찾기 (ex. 12453 에서 4와 5에서 오름차순이 됨 4 = k)
• k 와 k 값 다음으로 큰 수를 swap, 뒤 부분배열 오름차순 정렬
• 역순으로 정렬되어있을 때는 별도의 코드 필요
• constant memory 사용 조건을 지키지 못함

코드 1

    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        if n == 1: 
            return

        for i in range(n - 1, -1, -1):
            if nums[i] > nums[i - 1]:
                if i == 0: ## ex. 54321 
                    nums.sort()
                    return
                arr = sorted(nums[i:])
                idx = bisect.bisect_right(arr, nums[i - 1])
                nums[i - 1], arr[idx] = arr[idx], nums[i - 1]
                nums[i:] = arr
                return
  

        return res

접근 2 - Constant Memory

• 접근 1과 방식은 같음
• 다시 역순회를 시작하여 k 보다 큰 값을 찾아 swap (k 이후 값은 내림차순 되어있으므로 k 바로 다음으로 큰 숫자를 찾을 수 있음)
• 뒷 부분에 대해서 left 와 right 를 swap 하며 정렬 (sorted 쓰지 X, contant memory)

코드 2

    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = j = n - 1
        
        while k > 0 and nums[k] <= nums[k - 1]:
            k -= 1
        
        if k == 0:
            nums.sort()
            return
        
        k -= 1
        while nums[j] <= nums[k]:
            j -= 1

        nums[k], nums[j] = nums[j], nums[k]

        l, r = k + 1, n - 1
        
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
            r -= 1