Leetcode 75. Sort Colors (Dutch National flag, pointers)

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

Sort Colors - LeetCode

 

---

 

이 문제는 sort 없이  0,1,2로 대표되는 빨강,하얀,파랑 3가지 색깔 순서대로 정렬시키는 문제입니다

다른 문제와 달리, return 없이 값을 교체해야 한다는 조건이 붙어있습니다

 

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        colors = [0,1,2]
        cnt = {}
        for i in colors:
            cnt[i] = nums.count(i)
        
        new_nums = [i for j in [[i] * cnt[i] for i in colors] for i in j]
        
        for i in range(len(nums)):
            nums[i] = new_nums[i]

저는 count를 이용해서 색깔별 순서대로 색깔:개수를 매칭시켜서

새로운 리스트로 만들어서 교체하는 형식을 사용했습니다

 

ㅎㅎㅎ하지만 Leetcode문제는 그냥 넘어가지 않죠,,,,

이 문제는 Dutch national flag probelm에 해당하는 문제라고 합니다

이게 뭘 의미하는지 어떤 식으로 풀어나가야 하는지 살펴보겠습니다.

 

 

---

 

🧐  Dutch national flag problem 이란?

 

https://en.wikipedia.org/wiki/Dutch_national_flag_problem

 

Edsger Dijkstra에 의해 고안된 문제로 위에 네덜란드 국기처럼 빨강, 하얀, 파란 색의 공들이 랜덤하게 있을 때

국기에 있는 색의 순서에 알맞게 정렬하는 문제입니다.

 

다음과 같이 0, 1, 2 구간으로 나눠야 하는 리스트가 있다고 하면

low와 mid 포인터를 index 0에 위치시키고 high 는 가장 끝값에 위치시킵니다

 

이 때, 3가지 조건에 따라 순회를 진행합니다

 

1. mid 포인터의 값이 2 ==> 2를 현재 high 포인터의 위치로 보내고 high 위치를 -1이동합니다

2. mid 포인터값이 0 => 현재 low에 있는 값과 mid에 있는 값의 자리를 swap하고 low 위치를 +1, mid 위치를 +1 합니다

3. mid 포인터값이 1 => 단지 mid 포인터값의 위치를 +1 합니다

https://coderbyte.com/algorithm/dutch-national-flag-sorting-problem

 

위 3가지 법칙을 따른 과정이 그림에서 잘 나타나있는데요

법칙이 왜 나왔는지를 생각해보면

가장 중간의 mid를 기준으로 low는 가장 낮은 값의 다음위치, high는 가장 큰값의 시작위치에 있도록 swap하는

과정을 반복하는 것으로 볼 수 있습니다.

 

 

---

알고리즘에 대한 이해를 바탕으로 이 문제를 풀어보겠습니다

 

def sortColors(self,nums):
	low, mid, high = 0, 0, len(nums)-1
    
    while mid <= end:
    	if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            mid += 1
            low += 1
        elif nums[mid] == 2:
            nums[high], nums[mid] = nums[mid], nums[high]
            high -= 1
        else:
        	mid += 1

 

Dutch national flag problem의 원리를 차례대로 코드로 나타냈습니다.

 

 

 

Source:

https://en.wikipedia.org/wiki/Dutch_national_flag_problem