[LeetCode]Sort Colors

Sort Colors

풀이 생각

• 색이라고는 하지만, 어차피 정렬 함수를 사용하면, 0,0,1,1,2 이런식으로 정렬하게 된다. 따라서 그저 정렬을 구현하면 된다고 생각했다.
• 단순히 pivot을 첫 번째 원소로 하는 quicksort를 구현했다.

class Solution {
    // r,w,b 의 색으로 칠해진 n개의 objects가 주어졌을 때 
    // 이들을 in-place 로 sort하기.. 
    /*
    r,w,b의 순서로 정렬하고, 같은 색들끼리 정렬되도록 해야 한다. 
    각 색을 나타내기 위해 정수 0,1,2를 사용한다. 
    r : 0 
    w : 1
    b : 2 
    이 문제를 풀기 위해서는 라이브러리의 sort 함수를 사용해서는 안 된다 
    -----------
    
    quick-sort의 경우는 pivot을 찾아서 
    */
    public void sortColors(int[] nums) {
        if(nums==null || nums.length<2) return;
        quicksort(nums,0,nums.length-1);
    }
    // quick sort ---> pivot을 기준으로 left, right로 divdie 한다. 
    // pivot을 기준으로 left, right 구역을 생성합니다, 각 divide된 구역에서도 pivot을 기준으로 반복하여 정렬한다. 
    public void quicksort(int[] nums, int left, int right){
        // pivot을 기준으로 left, right를 나누어서 반복해야함 
        // 언제까지?? 
        if(left>=right) return; 
        int pivot = pivot(nums,left,right);
        quicksort(nums,left,pivot-1);
        quicksort(nums,pivot+1,right);
        
    }
    public void swap(int[]nums, int idx1,int idx2){
        int temp = nums[idx1];
        nums[idx1]=nums[idx2];
        nums[idx2]=temp; 
    }
    // 가장 좌측의 원소를 pivot으로 설정한다. 
    public int pivot(int[] nums,int left, int right){
        int pivot = left;      
        int l = left, h = right; 
        // 
        while(true){
            // nums[l]<=nums[pivot]이면 l을 우측으로 이동
            // l 은 right이하여야 한다. 
            while(l<=right&&nums[l]<=nums[pivot]){
                l++;
            }
            // h는 pivot보다 커야 한다 -> 따라서 pivot보다 작은 것을 탐색하면 stop  
            // nums[h]>=nums[pivot]이면 h을 좌측으로 이동 
            while(h>left&&nums[h]>=nums[pivot]){
                h--;
            }
            if(h>l){
                swap(nums,h,l);
            }
            else break; 
        }
        // if , h<l 이면 pivot과 h를 교환해야함. 
        if(h<l){
            swap(nums,h,pivot);
            pivot = h; 
        }
        return pivot;     
    }
    

}

--> 매우 좋지 않은 효율 을 가졌다.

다른 사람 풀이 (필수)

• 최대 3가지 종류의 원소만이 나오기 때문에 다른 사람의 idea는 이거였다.
• three pointer를 이용한다. two pointer중 하나는 0의 영역을, 하나는 2의 영역을 가리킨다. 나머지 하나의 포인터는 전체를 탐색하며 0과 2 영역으로 swap시키는 역할을 한다. 모든 0은 왼쪽으로 sweep시키고, 모든 2는 오른쪽으로 둔다. 그리고 모든 1들은 middle에다가 위치 시킨다.
• 어차피 0이 나오면, 어떤 0이던 그냥 왼쪽으로 이동시키기만 하면 된다.

• quicksort도 일종의 two pointer기법을 사용한다. 그것 처럼 생각 해 보자
• 이를 위해 2의 영역을 가리키는 pointer two , 0의 영역을 pointer zero를 둔다
  • 따라서, two는 배열의 가장 우측에 put, zero는 배열의 가장 좌측에 put 한다.

• i라는 pointer를 두고, i는 0부터 시작하여 increment시킨다.
• 먼저 모든 2를 우측에 위치시키는 과정이다. i가 2를 만나면, i는 two 와 swap 한다. -> 2는 two의 영역으로 이동하지만, two위치에 있던 것 또한 2일 수도 있는데 이것이 2로 가는 것이기에, two는 -- 시키고, i는 그대로 둔다. 그 상태에서 또 다시 같은 i 위치에 2 존재한다는 것은, 기존의 two에 0이 있었음을 의미한다. 이는 다시 two 영역으로 이동시켜줘야 하니 반복한다. 그러면서 two pointer는 감소시키므로 중복의 걱정은 없다. --> 따라서 two에 제약조건을 둬야 한다. two는 i 보다 클 때 까지만 이동한다.
• 같은 i 에 대하여 i 가 0을 만나면,i는 zero 와 swap한다. 만약 swap후에도 i 위치가 0이라면, zero만을 증가시키며, 또다시 같은 i 위치에 0이 오지 않을 때 까지 이동시키며 i와 swap한다. 또 다시 같은 i 위치에 0이 존재한다는 것은, 기존의 zero에 0이 있었음을 의미한다. 이는 다시 zero 영역으로 이동시켜줘야 하니 반복한다. 그러면서 zero pointer는 increment하니 중복의 걱정은 없다. --> zero에 제약조건을 둬야 한다. zero 는 i이하의 존재여야 한다.
• 즉, 모든 , n개의 원소에 대하여, 2인지 0인지를 확인해 나가는 과정으로 O(2n)의 시간복잡도를 갖는다 -> O(n) --> 위의 quicksort 구현보다 좋을 수 밖에 없다.

class Solution {

    public void sortColors(int[] nums) {
        if(nums==null || nums.length<2) return;
        int two = nums.length-1; 
        int zero = 0;
        for(int i=0;i<nums.length;i++){
            // swap후의 i 위치에 또 다시 2가 존재한다면 2는 우측으로 보내야 한다 
            while(nums[i]==2 && two>i) swap(nums,i,two--);
            // 1 0 1 2 인 경우 -> 0이 1의 우측에 있는 경우, 0을 zero 영역으로 보내야함
            while(nums[i]==0 && zero<=i) swap(nums,i,zero++);
        }
    }

    public void swap(int[]nums, int idx1,int idx2){
        int temp = nums[idx1];
        nums[idx1]=nums[idx2];
        nums[idx2]=temp; 
    }
}