94일 (75. Sort Colors) two pointers, quickSort

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

 

Example 1:

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

Example 2:

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

 

Constraints:

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

 

Follow up: Could you come up with a one-pass algorithm using only constant extra space?

 

 

- 접근방법

정렬해야 할 원소는 0, 1, 2 세개이므로 완전한 정렬 알고리즘을 구현하여 사용하는 것보다

투 포인터와 퀵소트의 원리를 이용하여 접근하였다.

(논리적으로 공간을 구분지으며 스왑하는 형식으로 접근하는 게 완전한 정렬알고리즘보다 공간복잡도에 이점이 있다.)

 

0. 배열 nums에 주어지는 원소는 3종류이므로 ptr1은 0을 가르키는 인덱스, ptr2는 1을 가르키는 인덱스, 그 외의 값인 2는 배열의 끝자락으로 넣었다. (포인터의 위치는 nums[ptr1+1] == 1, nums[ptr2+1] == 2 이다.)

 

1. 현재 ptr2가 가르키는 값이 0이라면?

현재 ptr2의 값과 현재 ptr1의 값을 스왑한 후 ptr1은 다음 인덱스를 가르킨다.(ptr1++)

ptr1이 다음 인덱스를 가르킨다면 자연히 ptr2의 논리적 공간도 1칸 밀려나기때문에 다음 인덱스를 가르켜야한다.

 

2. 현재 ptr2가 가르키는 값이 1이라면?

ptr1의 공간은 그대로이며, ptr2의 논리적인 공간이 하나 늘어나므로 ptr2는 ptr2++를 가르킨다.

 

3. 현재 ptr2가 2를 가르킨다면? 배열의 끝자락 인덱스와 현재 ptr2 인덱스의 값을 스왑한다.

배열의 끝자락의 숫자는 2이므로 더 이상 볼 필요가 없으므로 논리적으로 제외하기위해 n-- 을 한다.(n = array.length-1)

 

 

- 코드 

class Solution {
    public void sortColors(int[] nums) {
        int ptr1 = 0;
        int ptr2 = 0;
        int n = nums.length-1;

        while(ptr2 <= n) {
            if(nums[ptr2] == 0) swap(nums, ptr1++, ptr2++); // 1
            else if(nums[ptr2] == 1) ptr2++; // 2
            else swap(nums, ptr2, n--); // 3
        }
    }

    private void swap(int[] array, int firstIdx, int secondIdx) {
        int tmp = array[firstIdx];
        array[firstIdx] = array[secondIdx];
        array[secondIdx] = tmp;
    }

}

 

실제로 공간을 구분짓는 것이 아닌 포인터로 현재 공간의 위치를 가르키면서

논리적으로 공간을 구분짓는 것이 포인트이다.

 

 

 

 

https://leetcode.com/problems/sort-colors/

Sort Colors - LeetCode