Sort Colors | LeetCode 798 | Python3 🐍

 

📄 목차

 

 

 

🤔 문제 : Longest Palindromic Substring | LeetCode 780

문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/798/

주어진 배열을 정렬하는 문제입니다.

단, 이 문제에서 배열의 값은 0,1,2중 하나입니다. 

quick sort를 활용한다면 O(NlogN) 이 걸리겠지만, 배열의 값이 정해져있다는 점을 활용하여 더 빠르게 풀 수 있습니다.

 

💡 풀이

1.  hashMap활용, 0,1,2의 갯수 count

배열에서 나오는 값을 이미 알고 있기 때문에, 이를 활용해봅니다.

nums를 읽으며 0,1,2의 갯수를 저장하고,

한번 더 순회하며 갯수대로 세팅하는 방법입니다.

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        counts = {0: 0, 1: 0, 2: 0}
        for item in nums:
            counts[item] += 1

        index = 0
        for i in range(3):
            while counts[i] > 0:
                nums[index] = i
                index += 1
                counts[i] -= 1​

 

배열을 총 2번 순회하고, hashmap 크기만큼의 저장공간을 더 사용합니다. 

Time Complexity
O(N)

Space Complexity
O(1)

 

2.  one-pass algorithm

문제에 이런 단서가 달려있습니다. 

Follow up: Could you come up with a one-pass algorithm using only constant extra space?

 

배열을 한 번만 순회하면서 정렬을 해 나가는 방법도 있다는 얘기겠죠?

 

배열에 있는 원소가 세종류 밖에 없다는 점을 활용하면 아래와 같이 풀수도 있습니다.

• 0을 앞에서부터 채워나가며, 0이 채워진 인덱스 기록 (frontIdx)
• 0이 나오면 frontIdx의 값과 swap
• 2을 뒤에서부터 채워나가며, 2가 채워진 인덱스 기록 (backIdx)
• 2가 나오면 backIdx 값과 swap

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        backIdx = len(nums) - 1
        frontIdx = 0
        currIdx = 0
        while 1:
            if currIdx > backIdx: break
            if nums[currIdx] is 0:
                nums[frontIdx], nums[currIdx] = nums[currIdx], nums[frontIdx]
                frontIdx += 1
            if nums[currIdx] is 2:
                nums[backIdx], nums[currIdx] = nums[currIdx], nums[backIdx]
                backIdx -= 1
                currIdx -= 1 	[1] 주의!
            currIdx += 1

        print(nums)

[1] 2를 swap하고 나면 currIdx자리의 값에 뭐가 들어올 지 알 수 없습니다. 따라서, 해당 값은 다시 봐주기 위해 -1해줍니다.

 

time complexity는 동일하게 O(N)이지만, 전체 배열을 한 번만 순회하면 되므로 수행속도는 조금 더 빨라집니다.

 

3.  2번 살짝 개선 ,, 

2번 풀이에서 2가지를 개선해보겠습니다. 

• nums의 앞부분이 0인 경우 skip
• nums의 뒷부분이 1인 경우 skip
• 0과 0을 swap하는 경우 skip

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        if not nums: return nums
        backIdx = len(nums) - 1
        frontIdx = 0
        currIdx = 0
        while frontIdx <= backIdx and nums[frontIdx] is 0 : frontIdx += 1
        while frontIdx <= backIdx and nums[backIdx] is 2:  backIdx -= 1
        currIdx = frontIdx
        while currIdx <= backIdx:
            if nums[currIdx] is 0:
                if currIdx is not frontIdx:
                    nums[frontIdx], nums[currIdx] = nums[currIdx], nums[frontIdx]
                frontIdx += 1
            if nums[currIdx] is 2:
                nums[backIdx], nums[currIdx] = nums[currIdx], nums[backIdx]
                backIdx -= 1
                currIdx -= 1
            currIdx += 1

 

워낙 풀이들끼리 수행속도  차이가 미미해서인지, 이렇게 바꿨더니 93%로 올라갔네요.