리트코드 75번 Sort Colors (python)

Problem

LeetCode - The World's Leading Online Programming Learning Platform

Solution

내 풀이

from typing import List

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        for idx in range(len(nums)):
            curr = idx
            while curr > 0 and nums[curr] < nums[curr-1]:
                nums[curr], nums[curr-1] = nums[curr-1], nums[curr]
                curr -= 1

주어진 리스트의 원소를 하나씩 탐색하며 자신의 앞에 있는 원소들과 비교하여 정렬하였다. $O(n^2)$이 풀이 방식으로 성능이 좋지는 않다.

다른 풀이

from typing import List

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        red, white, blue = 0, 0, len(nums)

        while white < blue:
            # red
            if nums[white] < 1:
                nums[red], nums[white] = nums[white], nums[red]
                white += 1
                red += 1

            # blue
            elif nums[white] > 1:
                blue -= 1
                nums[white], nums[blue] = nums[blue], nums[white]
            
            # white
            else:
                white += 1

세 부분으로 분할(Three-Way Partitioning)하여 퀵 소트의 두 부분 분할을 개선한 방식을 이용하면 더 빠르게 풀이할 수 있다. 세 부분의 포인터를 각각 가지고 비교하며 탐색하면 $O(n)$의 시간 복잡도로 정렬할 수 있다.

Reference

파이썬 알고리즘 인터뷰 63번