[LeetCode]Next Permutation

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

Next Permutation - LeetCode

 

문제 분석

숫자가 주어졌을 때 다음 순열을 찾는 문제입니다.

 

처음 시도한 답안

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i = j = len(nums)-1
        while i > 0 and nums[i-1] >= nums[i]:
            i -= 1
        if i == 0:   # nums are in descending order
            nums.reverse()
            return 
        k = i - 1    # find the last "ascending" position
        while nums[j] <= nums[k]:
            j -= 1
        nums[k], nums[j] = nums[j], nums[k]  
        l, r = k+1, len(nums)-1  # reverse the second part
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
            r -= 1

접근 방법

1. nums 뒤에서부터 탐색하면서 오름차순이 깨지는 지점을 찾습니다.
2. 위 지점은 i-1 이고 k로 설정합니다.
3. 만약 i가 0 까지 도달한다면 내림차순으로 정렬이 된 상황(가장 뒤에 위치한 순열인 상황)입니다. 따라서 배열을 뒤집습니다.
4. i가 0이 아니라면, 이번에는 뒤에서부터 k 지점의 숫자보다 처음으로 커지는 지점을 j를 찾습니다.
5. k 와 j 지점의 값을 스왑합니다.
6. k+1 지점부터의 값을 reverse 합니다.

이 문제의 경우 다음 순열을 구하는 알고리즘을 알고 있어야 풀이할 수 있습니다. 알고리즘의 중요한 포인트는 다음과 같습니다.

 

1. 순열의 뒤에서부터 탐색하면서 뒤에서부터 보았을 때 오름차순이 처음으로 깨진 숫자(지점)인 k를 구합니다.
2. 순열의 뒤에서부터 k값보다 큰 요소를 처음으로 만나는 지점 j를 구하고, k와 j를 스왑합니다.
3. k+1 지점들의 값을 reverse 하면 다음 순열을 구할 수 있습니다.

nums = [1,2,3,6,9,5,4,0] 의 다음 순열은?

1. 오름차순이 처음으로 깨지는 지점 k = 3, k_value = 6
2. k_value(6)보다 처음으로 큰 요소 j = 4, j_value = 9
3. k와 j를 스왑. nums = [1,2,3,9,6,5,4,0]
4. k+1(4번째 인덱스) 지점부터 이후의 값들을 reverse. nums = [1,2,3,9,0,4,5,6]