IT/자기계발 ( Leetcode )
2021-01-31] Next PermutationSolution
Bell_bear
2021. 2. 1. 00:06
반응형
오늘의 문제:
이번 문제의 난이도는 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() # 먼저 주어진 배열이 가장 마지막의 순열이면 처음으로 돌아간다.
반응형