[LeetCode]Sort Colors

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

Sort Colors - LeetCode

 

문제 분석

주어진 nums 배열에 담긴 color들을 인접하도록 정렬하는 문제입니다.

 

처음 시도한 답안

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        color_count = {
            0:0,
            1:0,
            2:0,
        }

        for num in nums:
            color_count[num] += 1

        idx = 0
        for _ in range(color_count[0]):
            nums[idx] = 0
            idx += 1

        for _ in range(color_count[1]):
            nums[idx] = 1
            idx += 1

        for _ in range(color_count[2]):
            nums[idx] = 2
            idx += 1

접근 방법

1. nums 배열을 순회하면서 각 컬러가 얼마나 존재하는지 카운트합니다.
2. 카운트한 컬러를 가지고 nums 배열을 정렬시킵니다.

각 숫자별 갯수를 세어서 배열의 값을 변경시키는 가장 쉬운 방법으로 풀이했습니다. 다만, One-pass 알고리즘에는 부합하지 않는 것 같아서 솔루션을 참고했습니다.

 

두번째로 시도한 답안

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # Dutch National Flag Algorithm 그대로 구현

        start = 0 # red
        mid = 0 # white
        end = len(nums)-1 # blue
        
        while mid <= end:
            if nums[mid] == 0:
                nums[start], nums[mid] = nums[mid], nums[start]
                mid += 1
                start += 1
            elif nums[mid] == 1:
                mid += 1
            else:
                nums[mid], nums[end] = nums[end], nums[mid]
                end -= 1

접근 방법

1. Dutch National Flag 알고리즘을 이용합니다.
2. white가 blue 보다 작거나 같은 경우에만 반복합니다.
3. 0을 발견한 경우라면
   1. red 와 white 위치에 있는 nums를 스왑합니다.
   2. red, white를 1씩 증가합니다.
4. 1을 발견한 경우라면
   1. white를 1 증가합니다.
5. 2를 발견한 경우라면
   1. white 와 blue 위치에 있는 nums를 스왑합니다.
   2. blue를 1 감소합니다.

mid(white) 포인터를 움직이면서 start(red)와 end(blue)의 위치를 변경하는 것이 핵심입니다.

- 현재 mid가 0(red)인 경우라면 start와의 위치변경을 통해 red를 앞으로 white를 뒤로 보냅니다.
   (2개가 정렬이 되었으므로, start와 mid를 1씩 증가시킵니다.)

- 현재 mid가 1(white)인 경우라면 정렬이 잘 된것이므로 mid값만 1 증가시킵니다.

- 현재 mid가 2(blue)인 경우라면 end와의 위치변경을 통해 white를 앞으로 blue를 뒤로 보냅니다.

   (가장 뒤의 1개가 정렬이 되었으므로, end를 1 감소시킵니다. white는 앞으로만 위치한 것이고 정렬이 되었다고는 보장할 수 없습니다.)

 

네덜란드 국기 문제라는 특정한 알고리즘을 알아야 One pass로 풀 수 있는 문제입니다. 간단하기에 한번쯤은 익혀두는 것이 좋을 것 같습니다.