[Two Pointer 문제] LEETCODE.75. Sort Colors

문제풀이

이번 문제는 투 포인터를 활용하여 정렬 처리를 할 수 있는지에 대한 문제였다.(이 문제는 단순 버블정렬 등의 알고리즘을 통해 처리하더라도 Pass가 됨.)
해당 문제 접근시 일단 0은 무조건 왼쪽으로 배치하고 2는 오른쪽으로 배치하도록 처리하고자 하였다.
변수는 크게 3가지 변수로 선언하였다.
Lower Bound 인덱스를 의미하는 a,Upper Bound 인덱스를 의미하는 b 그리고 탐색하는 목적의 인덱스 i 변수이다.
알고리즘 동작 방식은 하기와 같다.
1. 최초 하한,상한,탐색 3가지 변수 선언
2. 탐색변수가 0을 만나면 하한과 교체하고 하한 범위를 +1
3. 탐색변수가 2를 만나면 상한과 교체하고 상한 범위를 -1
4. 탐색변수가 상한보다 크게 되면 탐색 종료

해당 알고리즘에서는 아래 3가지를 목표로 움직이게 된다. 만약 탐색변수가 b보다 크게 되면 2,3번의 목적이 달성되지 않고 2가 1보다 이전에 위치하게 되므로 종료하여야 한다.
1) 배열의 첫 글자 ~하한 인덱스 전까지는 0으로 이미 정렬된 상태
2) 하한 인덱스 ~ 탐색변수 전까지는 1로 채워진 상태
3) 상한 인덱스+1 ~ 마지막 변수까지는 2로 정렬된 상태

코드

1. 제출 소스
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i,a,b=0,0,len(nums)-1       
        
        while(i<=b):
            if nums[i]==0:
               # print("k",i)
                nums[a],nums[i]=nums[i],nums[a]
                a+=1
                i+=1
                #print(nums)                
            elif nums[i]==2:
                nums[b],nums[i]=nums[i],nums[b]                
                b-=1            
            else:
                i+=1



2. 속도 개선 버전
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i,a,b=0,0,len(nums)-1    

        while(i<=b):
            if nums[i]==0  and i > a:
               # print("k",i)
                nums[a],nums[i]=nums[i],nums[a]
                a+=1
                #print(nums)                
            elif nums[i]==2  and i < b:
                nums[b],nums[i]=nums[i],nums[b]                
                b-=1            
            else:
                i+=1        
            

Lookback

1. 투 포인터 문제에서 흔히 상한,하한 변수만 선언하였는데 탐색 변수를 추가로 선언하여 문제를 해결하는 측면에서 재미있었다.
2. 최초에 단순 정렬 문제 같은데 좋은 문제는 아닌 거 같다는 생각을 했었다. 하지만 배열 요소값이 0,1,2로 지정된 부분 등에 의미가 있을 듯하여 투 포인터 문제로 접근하였는데 이 문제는 네덜런드 국기 문제(Dutch National Flag Problem)'와 동일한 문제였다. 확실히 문제가 좋다 나쁘다 평하기 보다 의미를 찾는 태도가 중요한 것 같다.
3. 내가 제출된 코드에 대해 개선 포인트가 있다고 생각하였다. 가령 0,0,1,2,1,2,2 처럼 배열이 존재한다고 했을때 0,0,1,2,1,2,2 이렇게 정렬된 건 제외하고 풀 수 있지 않을까 싶었고 ChatGpt한테 의뢰하니 위 개선된 코드를 제공해주었다. 나는 처음 변수 선언시에 반복문으로 범위를 좁히는 작업을 할까 하였는데 ChatGpt는 i>a, i<b 조건 추가만으로 하나의 반복문에서 처리하는 아이디어가 참신하다고 생각했다.