[LC] 75. Sort Colors

[seungriyou]

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

Approach

Idea 1: Two-Pass

세 가지 종류의 int 값을 정렬하는 것이므로 counting sort를 적용하기 편리하다.

다음과 같이 두 번에 pass에 걸쳐 수행한다.

1. 0, 1, 2가 각각 몇 번 등장하는지 nums를 순회하며 카운트한다. (index로 사용하기 좋은 숫자이므로 list 사용)
2. 카운트 결과를 이용하여 주어진 nums를 in-place로 변경한다.

Idea 2: One-Pass (DNF) 💡

follow-up constraint

DNF(Dutch National Flag) Problem 📌

nums의 왼쪽부터 red(0), white(1), blue(2) 순서로 구성해야 하므로, O(1) space 조건을 만족하기 위해 pointer를 이용한다.

각 pointer의 이름을 red, white, blue라고 했을 때, 각 pointer의 역할은 다음과 같다.

이름	역할	초기값
red	확실하게 red인 원소의 오른쪽 원소를 가리킴 (즉, nums[red - 1] 까지 확실하게 red)	0 (맨 처음)
blue	확실하게 blue인 원소의 왼쪽 원소를 가리킴 (즉, nums[blue + 1] 까지 확실하게 blue)	len(nums) - 1 (맨 마지막)
white	왼쪽에서부터 이동하면서, 가리키는 원소의 색깔이 red인지 blue인지에 따라 red와 blue가 가리키는 원소와 swap 한다.	0 (맨 처음)

그리고 white pointer가 가리키는 원소의 색깔에 따라 다음과 같이 움직이며 in-place로 원소를 swap 한다.

이때, white는 blue까지만 이동해야 한다! 🚨

while white <= blue:
    # (1) nums[white]가 red를 가리키는 경우
    if nums[white] == 0:
        nums[red], nums[white] = nums[white], nums[red]
        red += 1        # nums[red - 1] 까지가 확실한 red가 됨
        white += 1

    # (2) nums[white]가 white를 가리키는 경우
    elif nums[white] == 1:
        white += 1

    # (3) nums[white]가 blue를 가리키는 경우
    else:
        nums[white], nums[blue] = nums[blue], nums[white]
        blue -= 1       # nums[blue + 1] 까지가 확실한 blue가 됨

Complexity

• Time: O(n)
• Space: O(1)