[LeetCode 풀이/python] 31. Next Permutation (medium)

문제 설명: 주어진 숫자 배열 nums 를 사전 편찬 기준 상 바로 다음에 올 숫자가 되도록 재배열하는 함수 next permutation 을 구현하시오. 만약 그러한 재배열이 불가능 하다면, 가장 낮은 순서로 (i.e. 오름차순) 재배열해야 하며, 이 때 재배열은 O(1) 의 추가 메모리만을 사용하여 제자리(in-place) 에서 이루어져야 함. 

 

(Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

The replacement must be in place and use only constant extra memory.)

 

예시 1)

입력: nums = [1,2,3]  --> 출력: [1,3,2]

 

예시 2)

입력: nums = [3,2,1]  --> 출력: [1,2,3]

 

예시 3)

입력: nums = [1,1,5]  --> 출력: [1,5,1]

 

예시 4)

입력: nums = [1]  --> 출력: [1]

 

제한 조건:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

 

------ * ------ * ------ * ------

 

[풀이 1안]

• 접근법
  1. 기본적으로 nums[i-1] > nums[i] 인 상황에서는 앞뒤 두 숫자를 교환(swap) 한 결과가 오히려 원 숫자보다 작아지므로, 배열의 맨 뒤에서부터 차례로 탐색하며 처음으로 nums[i-1] < nums[i] 가 되는 i 를 찾는다  -->  nums[i-1] < nums[i] 를 만족하게 되면 두 자리의 숫자를 교환!
  2. 사전 순서상 바로 다음에 올 숫자가 되려면 nums[i-1] > nums[i] 일 뿐만 아니라, min(nums[i-1], nums[i+1:]) 가 nums[i-1] 자리에 위치해야 하므로, nums[i-1] 을 nums[i+1:] 와 차례로 비교 & 교환하며 결과적으로 nums[i-1] 자리의 최적값을 찾아냄  -->  nums[:i] 까지 재배치 완료
  3. 이후 nums[i:] 부분을 오름차순으로 (==최저값) 마저 재배열 해야 하나, step 2 결과 nums[i+1:] 부분은 내림차순 정렬되어 있게 되므로, 우선 nums[i] 를 nums[i+1:] 와 차례로 비교 & 교환하여 nums[i:] 부분을 내림차순 정렬함
  4. nums[i:] 부분을 앞뒤 한 칸씩 교환하는 방식으로 내림차순 -> 오름차순 정렬화
  5. i == 1 인 경우 nums[i-1] & nums[i] 교환 이후 추가적으로 정렬 필요한 꼬리 부분이 없으므로 step 3,4 불필요
  6. step 1 에서 탐색 결과 nums[i-1] < nums[i] 을 만족하는 i 가 없는 경우 재배열 불가능  -->  전체 오름차순으로 재배열

 

• 코드 구현

def nextPermutation(nums: List[int]) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    
    n = len(nums)
    if n == 1: return nums
    
    for i in range(1, n):
        # step_1
        if nums[n-1-i] < nums[n-i]:
            nums[n-1-i], nums[n-i] = nums[n-i], nums[n-1-i]
            
            # step_2
            if i > 1:
                for j in range(1, i):
                    if nums[n-i+j] > nums[n-i]:
                        nums[n-i+j], nums[n-i-1] = nums[n-i-1], nums[n-i+j]
                
                # step_3    
                k = i
                while (k > 1) and (nums[n-k] < nums[n-k+1]):
                    nums[n-k], nums[n-k+1] = nums[n-k+1], nums[n-k]
                    k -= 1
                
                # step_4
                for s in range(i//2):
                    nums[-i+s], nums[-(s+1)] = nums[-(s+1)], nums[-i+s]

            return nums
            
            else:
                pass
            
        # if impossible
        return reverse(nums)
 
 
def reverse(nums):
    k = len(nums) // 2
    for i in range(k):
        nums[i], nums[-i-1] = nums[-i-1], nums[i]
    
    return nums 

 

• 결과
  • 숱한 에러 케이스 발견 & 디버깅 끝에 discussion 참고하지 않고도 무사히 통과...! >_<
  • 시간 & 공간 복잡도도 효율적인 코드라 더욱 뿌듯...! >_< (시간 복잡도는 최악 O(n^2) 인 것 같은데 이게 최선인가봉가...)