[LeetCode] Sort Colors

목차

문제

• 공간복잡도를 O(1)로 정렬하는 문제입니다. 0,1,2 으로 구성된 array가 있을 때 정렬하는 문제입니다.
  • 대부분의 정렬
• 예시
  

  • Input: nums = [2,0,2,1,1,0]
    Output: [0,0,1,1,2,2]

  • Input: nums = [2,0,1]
    Output: [0,1,2]

• 제약사항
  • n == nums.length
  • 1 <= n <= 300
  • nums[i] is either 0, 1, or 2

문제 풀이

풀이 1 : One Pass

• 풀이
  • 이 방식을 적용하면 시간복잡도 O(N), 공간복잡도 O(1)만에 해결이 가능합니다.
  • 단순하게 배열 안에는 3개의 값이 존재하기 때문에 2개의 경계를 두어서 정렬을 진행할 수 있습니다.
    • 먼저 p0= 0 , p2 = len(arr)-1에서 진행하고, curr는 p2보다 커질 때까지 진행합니다.
    • arr[curr] 값이 0일 경우, arr[p0]와 swap을 진행시켜 주고(앞쪽으로 보내기) p0+=1, curr+=1을 진행시켜 줍니다.
    • arr[curr] 값이 2일 경우, arr[p2]와 swap을 진행시켜 줍니다.(뒤쪽으로 보내기) 그 후 p2-=1을 진행시켜줍니다. curr+=1을 하지 않는 이유는 해당 값을 swap 하면 curr부분에 뒤에 있던 값이 오기 때문에 다시 체크를 진행해야 합니다.
    • arr[curr] 값이 1이면 curr를 그냥 1 증가시켜 줍니다. p0의 앞부분이 모두 0으로 정렬된 상태이기 때문에 1인 경우는 그대로 두면 됩니다.
  • 
• 코드

  • class Solution:
        def sortColors(self, arr: List[int]) -> None:
            p0 = curr = 0
            p2 = len(arr)-1
            while curr<=p2:
                if arr[curr]==0:
                    arr[p0],arr[curr]=arr[curr],arr[p0]
                    p0+=1
                    curr+=1
                elif arr[curr]==2:
                    arr[p2],arr[curr]=arr[curr],arr[p2]
                    p2-=1
                elif arr[curr]==1:
                    curr+=1

알게 된 내용

• arr 안에 값이 3개밖에 없을 경우는 경계를 2개 두어서, 단순하게 시간복잡도는 O(N), 공간복잡도는 O(1)만에 정렬이 가능합니다.

출처

• https://leetcode.com/explore/learn/card/sorting/694/comparison-based-sorts/4483/