75. Sort Colors

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Follow up:

• Could you solve this problem without using the library's sort function?
• Could you come up with a one-pass algorithm using only O(1) constant space?

My Answer 1: Accepted (Runtime: 32 ms - 72.69% / Memory Usage: 14.2 MB - 37.18%)

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

sort 로 힘차게 시작해봅니다~~

My Answer 2: Accepted (Runtime: 40 ms - 11.97% / Memory Usage: 14.1 MB - 65.32%)

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        for i in range(0, len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] > nums[j]:
                    temp = nums[i]
                    nums[i] = nums[j]
                    nums[j] = temp

이중 for 문이도 불러봤어요~~

런타임 웁스~~^^

My Answer 3: Accepted (Runtime: 40 ms - 11.97% / Memory Usage: 14.3 MB - 37.18%)

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        for end in range(1, len(nums)):
            for i in range(end, 0, -1):
                if nums[i - 1] > nums[i]:
                    nums[i - 1], nums[i] = nums[i], nums[i - 1]

Answer 2 와 유사하지만 비교대상 값의 앞부분을 확인하는 삽입정렬 기법~~

별도의 추가 공간을 사용하지 않고 주어진 배열이 차지하고 있는 공간 내에서 값들의 위치만 바꾸기 => O(1)의 공간 복잡도

이기 때문에 Answer 1, 2 모두
without using the library's sort function & using only O(1) constant space 는 만족함

come up with a one-pass algorithm 는 어떻게 해야할지 찾아보렵니다..

Solution 1: Runtime: 24 ms - 98.01% / Memory Usage: 14.1 MB - 88.16%

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # get amount of 0, 1, 2
        count = collections.Counter(nums)
        # replace in-place 
        for i in range(len(nums)):
            if i < count[0]:
                nums[i] = 0
            elif i < count[0] + count[1]:
                nums[i] = 1
            else:
                nums[i] = 2

collections.Counter 를 이용한 방식

0, 1, 2 세가지 색만 있으므로 count[0], count[1], count[2] 의 값을 기준으로 nums 값 바꿔주기

Solution 2: Runtime: 32 ms - 72.69% / Memory Usage: 14.1 MB - 65.32%

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        low,mid,high = 0,0,len(nums)-1
        while(mid<=high):
            if nums[mid] == 0:
                nums[low],nums[mid] = nums[mid],nums[low]
                low+=1
                mid+=1
            elif nums[mid] == 1:
                mid+=1
            else:
                nums[mid],nums[high] = nums[high],nums[mid]
                high-=1

low, mid, high 를 이용
nums[low] 는 0, nums[mid] 는 1, nums[high] 는 2로 잡으려는 듯