1053. Previous Permutation With One Swap

문제

나의 풀이

import heapq

class Solution:
    def prevPermOpt1(self, arr: List[int]) -> List[int]:
        h = []
        heapq.heappush(h, [arr[-1], -len(arr)+1, len(arr)-1])
        for i in range(len(arr)-2, -1, -1):
            if arr[i] > h[0][0]:
                target = []
                while h and h[0][0] < arr[i]:
                    target = heapq.heappop(h)
                arr[i], arr[target[2]] = arr[target[2]], arr[i]
                return arr
            else:
                heapq.heappush(h, [arr[i],-i, i])
                
        return arr

풀이 방법

내 풀이 방법은 매우 직관적이다.

1. priority heap을 이용해서 숫자를 관리 할 것이고
2. 배열의 가장 끝에서 시작할 것이며
3. priority heap에서 가장 작은 값보다 배열의 값이 클때 스왑이 이루어져야 한다.
4. priority heap에서 스왑될 숫자를 고르는 방법은
   1. 일단 가능한 가장 커야하고
   2. 같은 수라면 최대한 앞쪽 인덱스여야한다.
   3. 그래서 [값, -인덱스, 인덱스] 로 heap에 저장하여 관리한다.

다른 사람의 풀이

class Solution:
    def prevPermOpt1(self, arr: List[int]) -> List[int]:
        ind = -1
        for i in range(len(arr)-1,0,-1):
            if arr[i-1]>arr[i]:
                ind = i-1
                break
        else:
        	return arr

        for i in range(len(arr)-1,ind,-1):
            if arr[i]<arr[ind] and arr[i]!=arr[i-1]:
                arr[i],arr[ind] = arr[ind],arr[i]
                break

        return arr

개인적으로는 이 풀이가 매우 인상적이었다. 이렇게 생각한 것이 신기해서 한번 소개해 보겠습니다.

1. 일단 처음 for문으로 i-1의 값과 비교하여 i의 값이 작은 i를 ind에 저장하고 for문을 나옵니다.

2. for문이 break에 걸리지 않고 모두 실행 된다면 이미 가장 사전상 가장 작은 수로 배치된 배열이므로 그대로 리턴합니다.

3. len(arr)- ~ind+1로 index를 탐색하면서 arr[ind]값 보다 작은 값이 나오면 바로 ind와 값을 스왑하고 arr을 return합니다.

4. 이렇게 되는 이유는 우리가 첫 for문에서 확인 했던것 때문인데

   [1,1,1,1,4,3,3,3,3] 이린식의 배열이 있으면 ind의 값은 4가 된다.

   [1,1,1,1,4,1,2,3,4] 이런식으로 배열이 있어도 ind의 값은 4가 된다.

   [1,1,1,1,4,3,1,2,4] 이널식이면 ind의 값은 3이 된다.

   즉, ind의 값은 배열을 뒤에서 부터 탐색할때 값이 커지는 가장 첫 번째 index이며 배열 가장 뒷 숫자는 ind보다 큰 index들 중 가장 크거나 같은 숫자라는 것입니다.

   그래서 arr[ind]보다 작은 수가 나타나면 바로 스왑하는 것입니다.

   하지만 같은 수가 연속으로 나와있다면 가장 가까운 index와 스왑하는 것이 올바르므로 예외처리 해주었습니다.