[Leetcode][Java] 75 Sort Colors

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.

 

빨간색, 하얀색, 파란색으로 이루어진 n개의 요소를 가진 nums 배열이 주어진다.

새로운 배열을 선언하지 않고 제자리에서, 동일한 색이 서로 붙어 있도록 정렬을 하라.

순서는 빨간색 - 하얀색 - 파란색이다.

int값 0, 1, 2는 빨간색 - 하얀색 - 파란색을 나타낸다.

배열 기능이 존재하는 라이브러리를 사용하지 않고 문제를 풀어라. 

 

---

3개의 숫자로 이루어진 배열을 정렬해야 하는데, 추가적인 공간을 사용하지 않아야 한다.

배열의 맨 앞에 0과 swap할 포인터

배열의 맨 뒤에 2와 swap할 포인터를 둔다.

그리고 배열의 처음부터 끝까지 탐색할 포인터를 두어 해당 포인터의 값이 0이면 앞에 포인터와 swap

포인터의 값이 2이면 뒤에 포인터와 swap 하는 방식으로 문제를 해결할 수 있다.

다만, swap시 앞에 포인터에 해당하는 값은 탐색 포인터가 탐색한 값이므로 한번 더 체크할 필요가 없지만

뒤의 포인터와 swap한 값은 검증이 되지 않은 값이므로 체크해야 한다.

 

    public void sortColors(int[] nums) {
        int i = 0;
        int j = nums.length - 1;

        int p = 0;

        while (j >= p) {
            if (nums[p] == 0) {
                swap(i, p, nums);
                i++;
                p++;
            } else if (nums[p] == 2) {
                swap(j, p, nums);
                j--;
            } else {
                p++;
            }
        }
    }

    private void swap(int i, int j, int[] nums) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

 

문제 출처 : 

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

Sort Colors - LeetCode