[2024] day 165. leetcode 75. Sort Colors

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 6월 12일 (수)
Leetcode daily problem

75. Sort Colors

https://leetcode.com/problems/sort-colors/?envType=daily-question&envId=2024-06-12

Problem

빨간색, 흰색 또는 파란색으로 색상이 지정된 n개의 개체가 포함된 배열 nums가 주어지면 동일한 색상의 개체가 빨간색, 흰색, 파란색 순서로 인접하도록 해당 위치에서 정렬한다.

여기서는 정수 0, 1, 2를 사용하여 각각 빨간색, 흰색, 파란색을 나타낸다.
라이브러리의 정렬 기능을 사용하지 않고 이 문제를 해결해야 한다.

Solution

Dutch National Flag Algorithm

<Dutch National Flag Algorithm (네덜란드 국기 알고리즘)>

• 컴퓨터 과학에서 세 가지 색상(예: 빨강, 흰색, 파랑)으로 구성된 배열을 정렬하는 문제로, 색상을 기준으로 분할하는 것. 단일 패스로 배열을 정렬하고 일정한 추가 공간만 사용함
• 배열을 세 가지 부분으로 나누어 정렬하는데 0(빨강), 1(흰색), 2(파랑) 이라고 했을 때 이 세 가지를 세 개의 포인터("low", "mid", "high")를 사용해 배열을 분할함
• low는 0이 위치할 범위의 끝, mid는 현재 검사중인 요소, high는 2가 위치할 범위의 시작임
  - mid가 high보다 작거나 같을 때 까지 반복하는데, nums[mid] 가 0 이면 nums[low]와 nums[mid]를 교환하고 low, mid를 각각 +1 씩 증가시킴
  - nums[mid]가 1이면 mid를 1 증가시킴
  - nums[mid]가 2이면 nums[high]와 nums[mid]를 교환하고 high를 1 감소시킨 (이때 mid는 증가시키지 않는데, 교환된 nums[mid] 값이 확인되지 않았기 때문임)
  

Code

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[mid], nums[low] = nums[low], nums[mid]
                mid +=1
                low +=1
                
            elif nums[mid] == 1:
                mid +=1
                
            else:
                nums[mid], nums[high] = nums[high], nums[mid]
                high-=1

Complexicity

시간 복잡도

주어진 배열을 한 번 탐색하면서 정렬을 마무리하므로 시간복잡도는 O(n) 이다.

공간 복잡도

배열을 탐색할 때 추가적인 공간을 사용하지 않아 공간복잡도는 O(1) 이다.