[Grind75-LeetCode] Sort Colors JAVA

반응형

728x90

[Grind75-LeetCode] Sort Colors - Medium

---

접근

• Dutch National Flag

---

풀이

이 문제는 0, 1, 2가 들어있는 배열을 라이브러리의 sort 함수를 사용하지 않고 오름차순으로 정렬하면 되는 문제이다. 추가로 외부에 추가적인 공간을 사용하지 않고 배열 내부의 움직임으로만 one-pass 즉 한 번의 순회로 정렬해 보라는 추가 문제도 있다. 우선 Arrays.sort()를 사용해 제출을 해도 0ms의 최고 성능으로 통과는 가능하다. 그러나 문제의 취지와는 어긋나기에 라이브러리를 사용하지 않고 구현해야 한다.

 

우선 자바의 Arrays.sort()는 원시 타입 배열를 기준으로 Dual-Pivot QuickSort 알고리즘을 통해 정렬된다. Dual-Pivot QuickSort는 퀵 정렬의 변형된 알고리즘으로 한 개가 아닌 두 개의 피벗을 통해 정렬하게 된다. 그러나 퀵 정렬과 동일하게 평균 시간 복잡도로 O(n log n)를 가지기 때문에 one-pass 알고리즘으로 사용하기엔 적합하지 않다.

---

Dutch National Flag

이 번 문제는 Dutch National Flag 알고리즘으로 풀어진다. Dutch National Flag 알고리즘은 배열을 세 개의 구간으로 나누어 특정 순서대로 정렬하는 문제를 해결하기 위한 알고리즘이다. 이 알고리즘은 네덜란드 국기에서 이름을 따왔는데 국기의 색이 빨강, 하양, 파랑으로 세 가지 색상으로 구분되어 있다는 점에서 유래한 이름이다. 고로 이 알고리즘은 배열에서 세 가지 값만을 다룰 때 유용한 방법이다. 시간 복잡도 또한 O(n)으로 one-pass에 부합하는 방법이다. 

 

이 알고리즘의 핵심은 한 번의 순회로 세 가지 값을 분리하고 정렬하는 것으로 두 개의 포인터를 이용해 처리한다. 

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

low와 high 두 개의 포인터를 사용해 진행되고 low는 빨간색(0)을 처리할 구간의 끝을 가리키고 high는 파란색(2)을 처리할 구간의 시작을 나타낸다. i는 현재 처리중인 인덱스를 나타낸다.

	while (i <= high) {
            if (nums[i] == 0) {
                swap(nums, low, i);
                low++;
                i++;
            } else if (nums[i] == 2) {
                swap(nums, high, i);
                high--;
            } else {
                i++;
            }
        }

현재 인덱스 i가 파란색 처리 구간의 시작인 high 보다 작거나 같을 경우 처리는 계속된다. 만약 현재 값이 빨간색(0)이라면 현재 인덱스의 값을 low 인덱스의 값과 변경하고 low의 값을 올린다. 만약 현재 값이 파란색(2)이라면 현재 값과 high 인덱스 값을 변경하고 high 값을 내린다. 

//시작
i = 0 low = 0, high = 5
nums = [2,0,2,1,1,0]

i = 0, nums[0] = 2 -> high swap = nums[0] = 0, nums[5] = 2
high--, i++
low = 0, high = 4
nums = [0,0,2,1,1,2]

i = 1, nums[1] = 0 -> low swap = nums[1] = 0, nums[0] = 0
low++, i++
low = 1, high = 4
nums = [0,0,2,1,1,2]

i = 2, nums[2] = 2 -> high swap = nums[2] = 1, nums[4] = 1
high--, i++
low = 1, high = 3
nums = [0,0,1,1,2,2]
.
.

작업이 진행될 수록 low 보다 작은 인덱스는 다 빨간색(0)으로 바뀌게 되고 high 보다 큰 인덱스는 다 파란색(2)으로 바뀌게 된다. 

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

swap은 단순한 값 변경을 위한 함수이다. 

Dutch National Flag

---

전체 코드

class Solution {
    public void sortColors(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        int i = 0;

        while (i <= high) {
            if (nums[i] == 0) {
                swap(nums, low, i);
                low++;
                i++;
            } else if (nums[i] == 2) {
                swap(nums, high, i);
                high--;
            } else {
                i++;
            }
        }
    }

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