LeetCode 31(Next Permutation, Python)

1. 문제 링크

• LeetCode - The World's Leading Online Programming Learning Platform

Next Permutation - LeetCode

2. 문제 설명

• 주어진 수를 한 번씩 사용하여 배열하는 방법을 순열이라 한다.
• [1,2,3]이 주어지면 배열하는 방법은 [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] 순서로 존재함. 이때 [1,2,3]이 주어지면 그 다음 배열인 [1,3,2]로 수정하는 문제
• 예시) [1,2,3] → [1,3,2], [3,2,1]→[1,2,3], [1,1,5] → [1,5,1]
• 단, 메모리는 상수만 사용, in place 알고리즘으로 주어진 리스트를 조작

3. 처음 풀이

• 다음 순열은 그 값이 커진다(123<132). 예외적으로 마지막 순열은 다음 순열로 갈 때 작아지며 이 때는 역순이 결과임.(321 → 123)
• 두 수를 바꾸어 값이 커지려면 바꾸는 두 수 중 뒤의 것이 더 커야함.
• 따라서 앞에서 부터 살펴보며 그 수보다 오른쪽에 더 큰 수가 있는 지 관찰.
• 예를 들어 13524이면
  • 1보다 오른쪽에 더 큰 2 존재
  • 3보다 오른쪽에 더 큰 4 존재
  • 5보다 오른쪽에 더 큰 수 없음. 따라서 3을 바꾸어야 함.
  • 그런데 3 오른쪽에 있는 3보다 더 큰 수(5, 4) 중 가장 작은 4를 찾아 바꾸어야 함.
  • 그러면 14523이 됨. 이후 바뀐 자리인 4 오른쪽은 오름차순 정렬하여 14235를 반환

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        # 마지막으로 증가한 원소의 인덱스를 저장하는 변수
        last_increase_index = -1
        # 최소값을 저장하는 변수, 일단 무한대로 초기화
        min_value = float('inf')

        # 마지막으로 증가한 원소를 찾음
        for i in range(0, len(nums)-1):
            if nums[i] < max(nums[i+1:]) and last_increase_index < i:
                last_increase_index = i

        # 마지막으로 증가한 원소 이후에서 현재 원소보다 크면서 가장 작은 원소를 찾음
        for i in range(last_increase_index+1, len(nums)):
            if nums[last_increase_index] < nums[i] and nums[i] < min_value:
                min_value = nums[i]
                min_value_index = i

        # 만약 마지막으로 증가한 원소가 없다면 리스트를 정렬하여 최소 순열로 만듭니다.
        if last_increase_index == -1:
            nums.sort()
        # 그렇지 않으면 순열을 변경하여 다음 순열로 만듭니다.
        elif min_value < float('inf'):
            nums[last_increase_index], nums[min_value_index] = nums[min_value_index], nums[last_increase_index]

            # 변경된 부분 이후의 원소들을 오름차순으로 정렬하여 최소 순열을 만듭니다.
            for i in range(last_increase_index+1, len(nums)-1):
                temp = nums[i]
                temp_index = i
                for j in range(i+1, len(nums)):
                    if nums[j] < temp:
                        temp = nums[j]
                        temp_index = j
                nums[i], nums[temp_index] = nums[temp_index], nums[i]

4. 다른 풀이

• 내 풀이와 다르게 오른쪽부터 살펴보면 좀 더 자연스로운 로직이 가능하며, 오름차순을 할 때 reversed를 이용할 수 있다.
• 예) 13254
• 우선 오른쪽에서부터 거꾸로 갔을 때 작아지는 순간을 찾는다. 4에서 5로 갈 때는 커지고 5에서 2로 가면 작아진다. 이때 2의 index는 2이므로 pointer = 2로 설정
• 뒤에서부터 pointer전까지, 그러니까 4, 5 순서로 조회하며 pointer에서의 값(2)과 대소 비교
• pointer에서의 값보다 더 크면 포인터와 서로 바꾼 후 더 조회하지 않고 break
• 4는 2보다 크므로 서로 바꾸어 13452이고 pointer 값은 이제 4
• 이제 pointer 뒷부분 52은 역순하여 25로 바꾸어 13425

class Solution:
    def nextPermutation(self,nums):
        # Find the pivot point to perform swapping
        pivot = len(nums) - 2
        while pivot >= 0 and nums[pivot] >= nums[pivot + 1]:
            pivot -= 1

        if pivot >= 0:
            # Find the rightmost element greater than the pivot
            successor = len(nums) - 1
            while successor > pivot and nums[successor] <= nums[pivot]:
                successor -= 1
            nums[pivot], nums[successor] = nums[successor], nums[pivot]

        # Reverse the remaining elements to get the next permutation
        left, right = pivot + 1, len(nums) - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1
        '''
        마지막 Reverse 시키는 것은 위에서 처럼 직접해도 되고 아래와 같이 해도 된다.
        nums[pivot + 1:] = reversed(nums[pivot +1:])
        '''

        return nums

5. 배운 점

• reversed(list)를 이용하면 리스트를 역순 정렬 가능하다. 
• 정렬 방법으로 선택 정렬(Selection Sort), 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort), 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort)등이 있다. 
• 정렬 알고리즘에 대한 설명 위키, 나무위키
• 요약

	선택 정렬 (Selection Sort)	버블 정렬 (Bubble Sort)	삽입 정렬 (Insertion Sort)	병합 정렬 (Merge Sort)	퀵 정렬 (Quick Sort)
공간복잡도	O(1)	O(1)	O(1)	O(n)	O(logn)
평균 시간복잡도	O(n²)	O(n²)	O(n²)	O(nlogn)	O(nlogn)
최악 시간복잡도	O(n²)	O(n²)	O(n²)	O(nlogn)	O(n²)
최선 시간복잡도	O(n²)	O(n²)	O(n)	O(nlogn)	O(nlogn)
in-place (제자리 정렬)	in-place	in-place	in-place	not in-place	in-place
Stable (안정 정렬)	not stable	stable	stable	stable	not stable