31. Next Permutation

https://leetcode.com/problems/next-permutation/editorial/?envType=featured-list&envId=top-google-questions

input :

• nums

output :

• lexicographical order에 따른 다음 순열을 만드시오.

조건 :

• 반환값 없이 nums argument를 수정하는 것으로 확인을 함.

---

Solution explain : Solution1

idea

• solution에서 볼 수 있는 수도코드를 구현하자.
• a[k] < a[k + 1]을 만족하는 가장 큰 인덱스 k를 찾는다.
• a[k] < a[l]을 만족하는 가장 큰 인덱스 l을 찾는다.
• k와 l값을 swap하게 되면 nums[k + 1:]의 값은 계속 커져있는 수를 가지고 있게 된다.
  nums[k+1:]를 뒤집어서 넣는 방식으로 다음 순서의 순열을 가져올 수 있다.
  
  

reference : https://leetcode.com/problems/next-permutation/editorial/?envType=featured-list&envId=top-google-questions

주의

• k, l을 찾을 때는 뒤에서 부터 찾자.
• k를 None으로 초기화 했으니 is연산자를 써서 찾자. not연산자는 0값도 True로 바뀌게 한다.
• nums는 sort()로 정렬하자. 만약 현재 주어진 값이 가장 큰 순열이라면.

from typing import List


class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        k = None
        for i in range(len(nums) - 1, 0, -1):
            prev, now = nums[i - 1], nums[i]
            if prev < now:
                k = i - 1
                break

        if k is None:
            nums.sort()
            return

        l = None
        for i in range(len(nums) - 1, 0, -1):
            target, now = nums[k], nums[i]
            if target < now:
                l = i
                break

        nums[k], nums[l] = nums[l], nums[k]
        temp = nums[k + 1:][::-1]
        for i in range(k + 1, len(nums)):
            nums[i] = temp[i - (k + 1)]

s = Solution()
print(s.nextPermutation([1, 3, 2]))
print(s.nextPermutation([1, 2]))
print(s.nextPermutation([3, 2, 1]))
print(s.nextPermutation([1, 2, 3]))