2021-01-31] Next PermutationSolution

오늘의 문제:

leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/583/week-5-january-29th-january-31st/3623/

 

이번 문제의 난이도는 Medium 이지만, 순열에 대해서 잘 몰랐던 나는 이해하는데 어려움이 있었다.

 

문제 예시를 보며 이해한 내용을 공유한다.

 

숫자로 된 List nums 값이 주어지만, 그 다음번에 해당하는 순열을 구하면 된다.

 

예시 1번과 2번처럼 1,2,3이라는 원소로 만들 수 있는 순열은 총 6개이다.

[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] 

 

2번에서 다음 번 순열이 없을 경우, 처음거로 돌아온다.

 

원소 3개로는 너무 적으니 5개의 원소로 다시 이해해보자

 

[1,3,4,6,5,2] 의 다음 순열은 [1,3,5,2,4,6] 이된다.

 

순서적으로 변환을 할때 어떻게 되는 걸까?

 

우선 뒤의 값 2에서 부터 검사하여, 앞의 값과 비교했을때 앞의 값이 작은 index를 찾는다.

 

예제는 4가 될 것이다.  뒤를 떼어 놓는다면, [6,5,2] 가 된다.

 

이처럼 [6,5,2]는  저 원소들로 만들수 있는 가장 마지막 순열이다. (큰 순서로 정렬되어있음)

 

그 후  4와 가장 가까운 큰 수 5를 찾아, 두 값을 바꾸고 -> [1,3,5,6,4,2] ( 1차 변형 )

 

이후 바꿔진 [6,4,2]를 작은 순으로 정렬하면 된다 -> [1,3,5,2,4,6] ( 완료 )

 

이를 풀이한 코드는 아래와 같다.

 

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        for i in range(len(nums)-1,0,-1): # 뒤에서 역순 검사
            if nums[i]>nums[i-1]: # start index 구하기 ( 예시에서 4 뒤에서 첫 번째로 앞값이 더 작은 경우의 index ) )
                start=i-1
                for k in range(len(nums)-1,start,-1): # 자른 뒤의 배열 검사 
                    if nums[k]>nums[start]: # ( 예시에서 5  start와 가장 가까운 큰 값)
                        end=k
                        nums[start],nums[end]= nums[end],nums[start] # swap 
                        for m in range(int((len(nums)-start)/2)):
                            nums[start+1+m], nums[len(nums)-1-m] = nums[len(nums)-1-m], nums[start+1+m] # 정렬 
                        break
                break
            if i==1:
                nums.reverse() # 먼저 주어진 배열이 가장 마지막의 순열이면 처음으로 돌아간다.