31. Next Permutation

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

Next Permutation - LeetCode

Solution

class Solution:
    def nextPermutation(self, nums):
        temp = []
        for idx in range(len(nums)-1, 0, -1):
            if nums[idx] <= nums[idx-1]:
                temp.append(nums[idx])
                continue
                
            temp.append(nums[idx])
            
            for i, n in enumerate(temp):
                if n > nums[idx-1]:
                    temp[i], nums[idx-1] = nums[idx-1], n
                    for j in range(len(temp)):
                        nums[idx+j] = temp[j]
                    break
            break
        else:
            nums.reverse()

• 사전순으로 다음 순서를 결정하는 규칙을 찾는 것이 핵심이다.
• 뒤에서 하나씩 살펴보면서 요소를 temp에 저장한다.
• 이전보다 작은 값을 가지는 요소의 위치 idx-1를 찾는다.
• idx-1 이후의 값 중, idx-1의 값 바로 다음으로 큰 값을 찾는다.
• 그 값을 idx-1와 swap한다.
• idx-1 이후의 값을 정렬된 상태로 넣는다.

 

• for else에서 else는 break로 나갔을 때는 실행되지 않는다.
• reverse()를 통해 리스트의 값을 반대로 뒤집을 수 있다.

Another

class Solution:
    def nextPermutation(self, nums):
        i = j = len(nums) - 1
        while i > 0 and nums[i - 1] >= nums[i]:
            i -= 1
        if i <= 0:
            nums.reverse()
            return

        while nums[j] <= nums[i - 1]:
            j -= 1
        nums[i - 1], nums[j] = nums[j], nums[i - 1]

        nums[i : ] = nums[len(nums) - 1 : i - 1 : -1]

• 잘 알려진 좋은 알고리즘이다.
• i 를 감소시키면서 값이 작아지는 곳의 위치를 찾는다.
• j 를 감소시키면서 i 보다 큰 값이 나오는 곳의 위치를 찾는다.
• 둘을 swap 한다.
• i 위치 이후의 구간을 뒤집는다. => 내림차순으로 되어 있으므로 정렬과 같다.