63. Sort Colors

🎯 leetcode - 75. Sort Colors

---

📌 문제

- 파이썬 알고리즘 인터뷰 63번 문제
- red(0), white(1), blue(2)에 대하여 '제자리 정렬'을 수행하라.

📌 날짜

2020.02.28

📌 시도 횟수

Failed

💡 Code

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

        while white < blue:
            if nums[white] < pivot:
                nums[red], nums[white] = nums[white], nums[red]
                white += 1
                red += 1
            elif nums[white] > pivot:
                blue -= 1
                nums[white], nums[blue] = nums[blue], nums[white]
            else:
                white += 1

💡 문제 해결 방법

• 기본 문제 해결 방법
  
• [2, 0, 2, 1, 1, 0]을 위의 방법으로 정렬하기
  

- red, blue는 양쪽 포인터로 둔다. 값은 가장자리부터 확정된다. 왼쪽 값(0)이 확정되면
red가 한 칸 이동하고, 오른쪽 값이 확정되면 blue가 한 칸 이동한다.
- white는 움직이면서 실제 비교를 수행하는 포인터이다.
- 현재 white가 조사하고 있는 값이 pivot(1)보다 작으면 red가 한 칸 확정되고, 
pivot(1)보다 크면 blue가 한 칸 확정된다. 
- 만약 pivot(1)과 같다면 white만 한 칸 이동시킨다.
- white는 red(맨 앞)에서부터 시작하고, white가 blue에 도달하게 되면 정렬이 완료된다.

💡 새롭게 알게 된 점

- 해당 문제는 다익스트라의 '네덜란드 국기 문제'와 동일한 문제라고 한다.

• 네덜란드 국기 문제?

❌ (한번에 맞추지 못한 경우) 오답의 원인

- 문제 의도를 이해하기 어려웠다.
- 이런 풀이 방법은 처음 본다. 다시 풀어봐야겠다.

• ⭐퀵정렬 다시보기⭐

---