LeetCode 75(Sort Colors, Python)

1. 문제 링크

• https://leetcode.com/problems/sort-colors/

Sort Colors - LeetCode

 

2. 문제 설명

• 0,1,2 세 정수로 구성된 nums라는 array가 주어졌을 때, in-place로 sort library를 사용하지 않고 nums를 정렬하여 반환
  • 여기서 0이 red, 1이 white, 2가 blue를 나타내고 + 각 컬러가 인접하게 red, white, blue순으로 반환하라고 하는데,
  • 이 문제에서는 굳이 색으로 비유할 필욘 없었던 것 같다. 
• 예시1) nums = [2,0,2,1,1,0], output = [0,0,1,1,2,2]
• 예시2) nums = [2,0,1], output = [0,1,2] 

3. 처음 풀이 

• 처음에 생각한건 약간 tricky한 (뭔가 출제자의 의도는 이게 아니었을 것 같은) 방식이었다. 
• 그냥 0이 등장한 count, 1이 등장한 count를 세고,
  • nums를 for문을 돌리면서
  • index가 zero_count보다 작으면 0,
  • zero_count + one_count보다 작으면 1
  • 그 외의 경우는 2를 할당하는 것으로 코드를 작성했다.
• 다행히 통과는 했으나, 뭔가 이게 의도가 아니었을 것 같은 찜찜함과
• 어쨌든 count를 할 때에도 iterate를 도는 것이므로 3n 만큼의 Complexity를 가지는 것 같아서 더 개선이 필요했다.

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """

        zero_count = nums.count(0)
        one_count = nums.count(1)

        for index, i in enumerate(nums):
            if index < zero_count:
                nums[index] = 0
            elif index < zero_count + one_count:
                nums[index] = 1
            else:
                nums[index] = 2

4. 다른 풀이

• low, mid, high라는 3개의 pointer를 두고, 
• mid <= high일 때까지 (아래 로직 상 low는 항상 mid보다 값이 작을 수 밖에 없으므로, mid <= high가 while을 도는 조건문)
• 세 포인터의 위치를 조정해가는 것 → 이렇게 하면 iterate를 한번만 돌면서, in-place하게 해결이 가능하다.
  • nums[mid] 가 값이 0이면 low와 위치를 바꿔주고, low, mid를 한 칸씩 더한다.
  • nums[mid]의 값이 2이면, high와 위치를 바꿔주고, high를 한칸 뺀다.
  • mid 값이 1이면 그냥 mid를 한칸 오른쪽으로 옮긴다. 
• 이를 Dutch National Flag Algorithm이라고 한다. (그래서 문제에서 색깔 비유를 한 것이었다.)
  • 또 다른 말로는 Three-Way Partitioning Algorithm이라 하며,
  • 3개의 distinct한 element를 포함하는 배열을 sorting하는 가장 단순하고 효과적인 접근 방법이라고 한다.
    • 물론, 우리는 sort()라는 python 내장 library가 있기 때문에, 이걸 쓸일은 없겠지만, 알아두면 좋겠다!

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """

        low = 0 
        mid = 0
        high = len(nums)-1

        while mid <= high:
            if nums[mid] == 0:
                nums[mid], nums[low] = nums[low], nums[mid]
                low +=1
                mid +=1
            elif nums[mid] == 2: 
                nums[high], nums[mid] = nums[mid], nums[high]
                high -=1
            else:
                mid +=1

5. 배운 점

• Dutch National Flag Algorithm