leetcode : next-permutation

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

Next Permutation - LeetCode

 

아 진짜 permutation 문제는 너무 어렵다.. 내가 수학쪽에 약해서 그런가 ㅋㅋ..

이것까지만 풀고 회사 일 시작해야겠다.

 

이 문제는 시퀀스가 주어졌을 때 그 시퀀스의 다음 permutation을 찾는 문제다.

가령 1,2,3 이 주어지면 1,3,2를 정답으로 내놓아야되고 2,3,1이 주어지면 3,1,2를 내놓아야 되는 식이다.

 

근데 이게 참 까다로운게 조건이 붙어서다. 그냥 쌩노가다면 누구나 하지. 조건은 O(1)의 공간복잡도다. 당연히 정답리스트를 따로 만들면 안되고 인자로 주어진 리스트를 in-place로 수정해야된다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ예아

 

일단 1~4의 숫자를 가지고 permutation을 나열해보자. 규칙을 찾아야되는 문제니까.

1234

1243

1324

1342

1423

1432

2134

2143

2314

2341

...

4123

4132

4213

4231

4312

4321

 

일단 눈에 보이는 규칙은, 각 자리의 숫자가 작은 숫자부터 시작해서 점점 커진다는 것이다.

가령 첫 번째 자리 숫자는 1->2->3->4로 바뀌고, 첫 번째 숫자가 fix되어 있을 때 그 다음인 두 번째 자리 숫자는 2 -> 3 -> 4, 두 번째 숫자가 fix되어 있을 때 세 번째 자리 숫자는 3 -> 4.. 이런식이다.

 

특정 시퀀스가 주어졌을 때, 다음 시퀀스에서 몇 번째 자리 숫자가 바뀌어야 되는지는 어떻게 알 수 있을까?

실마리는 숫자의 '순서'에 있다. 위 permutation 시퀀스를 다시보자. 힌트를 드리겠다

 

123/4

12/43

132/4

13/42

142/3

1/432

213/4

21/43

231/4

23/41

..

 

저 슬래시를 무슨 기준으로 넣었는지랑 그 다음에 어떤 자리 숫자가 바뀌는지를 유심히 보자.

아직 규칙을 못 찾았는가?

극단적인 케이스를 살펴보자. (역시 규칙 찾을 땐 '극단'이 최고야)

가장 마지막 시퀀스는 뭘까? 4321이다. 4321이 주어졌을 때 이게 가장 마지막 시퀀스라는건 어떻게 알 수 있을까?

모든 숫자가 내림차순으로 쭉 나열되어있다! 그럼 가장 마지막 시퀀스인 것이다. 그럼 그 담엔 모든 숫자가 오름차순으로 나열되어있는 첫 시퀀스로 다시 돌아가야겠지.

 

자 다시! 핵심은 4개의 숫자의 시퀀스의 맨 끝은 그 숫자들이 모두 내림차순으로 나열되어 있는 경우라는 것이다.

그럼 첫 번째 숫자가 픽스된 상태일 때(가령, 1일 때) 마지막 시퀀스는 무엇일까? 1432이다. 1을 제외한 나머지 숫자들이 내림차순으로 나열된 것이다.

다시보자

123/4

12/43

132/4

13/42

142/3

1/432

213/4

21/43

231/4

23/41

 

굵은 글씨 친 부분의 순서가 어떻게 되어있는가?

내림차순이다!!

right-to-left 스캔을 해서 내림차순인 부분을 찾고나면 그 다음은 쉽다. 내림차순인 부분의 바로 왼쪽 숫자 (142/3의 경우 2, 21/43의 경우 1) 가 바뀔 차례다. 어떤 것으로 바뀔까? '내림차순인 부분의 바로 왼쪽 숫자'보다 큰 숫자로 바뀐다. 그 숫자는 내림차순인 부분에서 찾을 수 있다. 내림차순인 부분에 있는 숫자들 중에서 '내림차순인 부분의 바로 왼쪽 숫자'의 다음으로 큰 숫자를 찾으면 된다. 가령 21/43에서는 3,4중에 1 다음으로 큰 숫자는 3이므로 그 다음 시퀀스에서 1은 3으로 바뀌어야 한다. 실제로 2143 다음의 시퀀스는 2314로, 1이 3으로 바뀐 것을 확인할 수 있다.

 

정리해보자.

2143을 예시로 들겠다

1. 시퀀스를 '내림차순이 아닌 부분' / '내림차순인 부분'으로 나눈다.

2,1 / 4,3

 

2. 이걸 편의상 FIXED / DESC 파트라고 부르겠다.

FIXED = 2,1

DESC = 4,3

 

3. FIXED의 맨 오른쪽 끝 숫자를 보자. DESC에 있는 숫자들 중에서 FIXED오른쪽끝숫자 바로 다음으로 큰 숫자를 찾는다.

이 때, DESC 파트를 정렬을 해야 한다. 그래야 바로 다음으로 큰 숫자를 찾을 수 있다.

FIXED = 2,1

DESC = 4,3 -> 정렬 -> 3,4

2,1 / 3,4

 

4. FIXED의 맨 오른쪽 끝 숫자랑 DESC에 있는 숫자들 중에서 그보다 바로 큰 숫자를 스왑한다.

2, 1 / 3, 4 -> 2, 3 / 1, 4

 

아 근데 이게 in-place로 작업을 해야 되다 보니까 정렬을 내가 따로 구현해줘야되는 단점이..

제엔장! 퀵정렬 구현을 쉽게 하려면 이 글 참고 https://keep-your-pace.tistory.com/22

 

class Solution:
    def quicksort(self, array, start, end):
        ...어찌저찌 퀵정렬이 구현되어 있다 가정. 구현은 위 링크 참고
    
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if len(nums) == 1:
            return
        
        fixed_end = len(nums) - 1
        # fixed 파트의 오른쪽 끝 부분
        # right-to-left 스캔을 해야되니까 리스트의 맨 끝 인덱스로 초기화한다
        
        #fixed 파트의 오른쪽 끝을 찾는다
        while fixed_end > 0:
            if nums[fixed_end - 1] < nums[fixed_end]:
                break
            fixed_end -= 1
        fixed_end -= 1
        
        #모든 요소가 내림차순이면 시퀀스 끝이란 뜻
        if fixed_end == -1:
            nums.sort()
            return
        
        #정렬한다.
        self.quicksort(nums, fixed_end + 1, len(nums) - 1)
        

        #fixed_end 오른쪽 끝숫자보다 바로 다음으로 큰 숫자를 찾는다
        nextnum = fixed_end
        while nums[nextnum] <= nums[fixed_end]:
            nextnum += 1
        

        #fixed_end 오른쪽 끝숫자랑 위에서 찾은 숫자랑 스왑한다.
        tmp = nums[nextnum]
        nums[nextnum] = nums[fixed_end]
        nums[fixed_end] = tmp
        

 

참고로 이 문제는 다른 사람들의 풀이를 찾아봐도 짧고 단순하고 간결한 코드는 찾기 힘들다... 내가 잘했다는 건 아니지만 이 정도면 나쁘지 않은 것 같다.