[정렬] Leet code 75. Sort Colors

리트코드 75번
빨간색(0), 흰색(1), 파란색(2) 순서대로 제자리 정렬

처음에는 inplace이기때문에 퀵소트나 합병정렬을 해야하나 했지만 아무래도 0,1,2만으로 구성된 배열을 정렬하는데 거창하다는 생각도 들었고 더 간단한 방법이 있지 않을까.. 했다

풀이1

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        head ,tail = 0, len(nums)-1
        i = 0

        while i <= tail:
            if nums[i] == 0:
                if head == i: # 자리 교환이 필요 없는 경우 다음 것으로 가기
                    i = i+1
                else:
                    nums[head], nums[i] = nums[i], nums[head]
                head = head + 1
            elif nums[i] == 2:
                nums[tail], nums[i] = nums[i], nums[tail]
                tail = tail - 1
            else: # 1일때는 한칸 나아가기 
                i = i + 1

• 기본아이디어 : 0과 2를 양끝에 모으자
• 0, 2가 발견될때마다 양끝에 옮기기
• inplace정렬 -> swap을 사용해야겠다
• 양끝에 두개의 pointer로 위치를 저장해야겠다
• head, tail이 양끝에 위치를 기억, i는 앞에서부터 하나씩 검사
• swap기 때문에 i가 매번 ++되면 안되고 더이상 정렬을 할게 아닐때만 옮겨가야 한다 (1이거나 0,2가 제자리 일때)
• i가 tail보다 커지면 정렬이 끝났다는 의미

풀이2 코드개선

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        head ,tail = 0, len(nums)-1
        i = 0

        while i <= tail:
            if nums[i] == 0:
                nums[head], nums[i] = nums[i], nums[head]
                head = head + 1
                i = i + 1
            elif nums[i] == 2:
                nums[tail], nums[i] = nums[i], nums[tail]
                tail = tail - 1
            else: # 1일때는 한칸 나아가기 
                i = i + 1

• 0 swap 후 : 앞에서 정렬하면서 왔기 때문에 0 or 1이 i에 온다
  -> i 한칸 옮겨가면 된다
• 2 swap 후 : 아직 건드린적이 없는 곳과 교환했기 때문에 0,1,2다 올 수있다
  -> i 그대로 있어야한다