LeetCode: 75번 (Sort Colors) [JAVA]

문제 링크

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

Sort Colors - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 투 포인터 start, end를 각각 배열의 시작과 끝으로 설정
2. start < end인 동안 반복하여, 뒷 부분의 0을 앞으로 이동
   1) start 부분의 요소가 0이면 ++start
   2) end 부분의 요소가 0이라면 start 부분과 swap
   3) end 부분이 0이 아니라면 --end
3. 다시 end를 배열의 끝으로 설정하고, 다시 start < end인 동안 반복하여 뒷 부분의 1를 앞으로 이동
   1) start 부분의 요소가 1이면 ++start
   2) end 부분의 요소가 1이라면 start 부분과 swap
   3) end 부분이 1이 아니라면 --end
   

 단순히 정렬을 요구하는 문제이다. 다만 문제 상 라이브러리 내부 알고리즘을 사용하지 말 것을 요구한다. 그렇기 때문에 정렬을 직접 구현해야 하는데, 문제에 주어진 nums 배열에서 요소가 0, 1, 2 밖에 없기 때문에 훨씬 단순하게 구현할 수 있다.
 투 포인터를 사용해서, start와 end에 각각 배열의 시작과 끝을 설정한다. 이후 while문을 통해 start < end인 동안 배열 뒷 부분의 0을 앞으로 가져온다. 만약 start 위치의 요소가 0이라면 다음 start로 옮겨가고, 그 외에 만약 end 부분의 요소가 0이라면 start와 swap을 진행한다. 만약 end 부분의 요소도 0이 아니라면 end를 앞으로 옮긴다.
 이후에는 배열의 앞부분에 0이 모두 채워져 있고, 남은 구간에 1과 2가 섞여 있기 때문에, 다시 0이 없는 이후 구간부터 앞선 로직을 반복한다. end를 다시 배열의 끝으로 설정하고, 이후 while문을 통해 start< end인 동안 앞선 로직과 동일하게 1들을 앞으로 옮기면 된다.

 

class Solution {
    public void sortColors(int[] nums) {
        int start = 0, end = nums.length - 1;

        while (start < end) {//배열의 시작과 끝에서 비교해가며 0을 이동
            if (nums[start] == 0) {
                ++start;
            } else {
                if (nums[end] == 0) {
                    nums[end] = nums[start];
                    nums[start] = 0;
                    ++start;
                } else {
                    --end;
                }
            }
        }

        end = nums.length - 1;

        while (start < end) {//배열 속 0 이후 구간과 끝에서 비교해가며 1을 이동
            if (nums[start] == 1) {
                ++start;
            } else {
                if (nums[end] == 1) {
                    nums[end] = nums[start];
                    nums[start] = 1;
                    ++start;
                } else {
                    --end;
                }
            }
        }
    }
}

결과