leetcode medium : next permutation 복습

Next Permutation

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

풀기 전

몇 가지 observation을 해보면 쉽게 풀 수 있다.

 

Observation 1 : 오른쪽 파트가 내림차순 정렬된 상태가 되면 그 다음차례에 앞 숫자가 바뀐다.

Example

2 3 1 → 오른쪽 [3 1]이 내림차순 정렬된 상태

3 1 2 → 그 앞 숫자였던 2가 3으로 바뀌었다.

 

Observation 2 : Observation 1에서 앞 숫자가 바뀔 때는 오른쪽 숫자 중에 그 숫자 바로 다음으로 큰 숫자로 바뀐다.

Example

2 3 1 → 오른쪽 [3 1]이 내림차순 정렬된 상태, 다음에 그 앞 숫자인 2가 바뀌어야 된다.

이때 오른쪽 [3 1] 중에 2 다음으로 큰 숫자는 3이므로 3으로 바뀌어야된다.

3 1 2 → 그 앞 숫자였던 2가 3으로 바뀌었다.

 

Observation 3 : Observation 1에서 앞 숫자가 바뀐 뒤에 오른쪽 파트는 오름차순 정렬된다.

2 3 1 → 오른쪽 [3 1]이 내림차순 정렬된 상태

3 1 2 → 3 오른쪽 파트 [1 2]는 오름차순 정렬된 상태이다.

 

Observation 4 : 모든 숫자가 내림차순 정렬되어 있으면 다시 처음으로 돌아가 모든 숫자가 오름차순 정렬된 상태가 된다.

[4 3 2 1] → 모든 숫자가 내림차순

[1 2 3 4] → 모든 숫자가 오름차순 정렬된 상태가 그 next permutation이다.

코드 설명

여러 가지 버전으로 짜봤다.

 

1. 최대한의 효율 추구

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
				# 오른쪽에서 내림차순 정렬된 파트 찾기
        i = len(nums) - 1
        while i > 0:
            if nums[i] > nums[i - 1]:
                break
            i -= 1

				# 전부 다 내림차순이면 그냥 뒤집고 리턴
        if i == 0:
            for i in range(len(nums) // 2):
                tmp = nums[i]
                nums[i] = nums[-i - 1]
                nums[-i - 1] = tmp
            return

				# 이진탐색
        low = i
        high = len(nums) - 1
        while low <= high:
            mid = (low + high) // 2
            if nums[mid] > nums[i - 1] and (mid == len(nums) - 1 or nums[mid + 1] <= nums[i - 1]):
                j = mid
                break
            elif nums[mid] > nums[i - 1]:
                low = mid + 1
            else:
                high = mid - 1

				# 스왑
        tmp = nums[i - 1]
        nums[i - 1] = nums[j]
        nums[j] = tmp

				# 오른쪽 파트 오름차순으로
        for k in range(i, (i + len(nums)) // 2):
            nums[k], nums[len(nums)-(k-i)-1] = nums[len(nums)-(k-i)-1], nums[k]

for문을 가급적이면 덜 쓰고

튜플을 이용한 스왑이 아닌 클래식한 방법으로 스왑을 진행한다.

그리고 정렬된 부분에서 왼쪽 숫자보다 큰 숫자를 찾을 때 이진탐색을 이용한다.

오른쪽 정렬된부분이 길면 길수록 효율적인데

문제 테스트케이스가 그런 케이스가 많진 않은지 이진탐색 적용하고 속도가 확 느려졌다.

 

2.가장 빠른 속도가 나왔던 버전

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
				# 오른쪽 내림차순파트 찾기
        i = len(nums) - 1
        while i > 0:
            if nums[i] > nums[i - 1]:
                break
            i -= 1

				# 전부다 내림차순이면 뒤집고 리턴
        if i == 0:
            nums.reverse()
            return
	
				# 왼쪽 숫자보다 큰 숫자 찾고 스왑
        j = len(nums) - 1
        while nums[j] <= nums[i - 1] and j > i:
            j -= 1
        nums[i - 1], nums[j] = nums[j], nums[i - 1]

				# 오른쪽 파트 오름차순으로 정렬
        for k in range(i, (i + len(nums)) // 2):
            nums[k], nums[len(nums)-(k-i)-1] = nums[len(nums)-(k-i)-1], nums[k]

3. 극한의 간결함

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        for i in range(len(nums) - 1, 0, -1):
            if nums[i] > nums[i - 1]: break
        else: return nums.reverse()
        for j in range(len(nums) - 1, i - 1, -1):
            if nums[j] > nums[i - 1]: break
        nums[i - 1], nums[j] = nums[j], nums[i - 1]
        nums[i:] = nums[i:][::-1]

분석

시간복잡도 O(N)

공간복잡도 O(1)