75. Sort Colors

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

Sort Colors - LeetCode

난이도 : 미디움

문제

빨간색을 0, 흰색을 1, 파란색을 2라 할 때 순서대로 인접하는 제자리In-Place 정렬을 수행하라.

 해당 문제는 sort 를 이용해서 풀어도 해결 할 수 있다. 또한 map 자료형을 이용해서 원소를 모두 카운트하고 순서대로 출력만해도 문제는 풀린다. 하지만 이문제는 sort, map 에 자료형을 이용해서 푸는 문제가 아니라 인접하는 제자리In-Place 정렬을 구현하는 문제이다.

 다익스트라가 1976년에 제안한 '네덜란드 국기문제'와 동일한 문제로 퀵 정렬의 개선 아이디어와 관련이 깊은 문제이다. 피벗보다 작은 부분, 같은 부분, 큰 부분 이렇게 세 부분으로 분할하여(Three Way Partitioning)하여 기존 퀵 정렬의 두 부분 분할에 비해 개선하는 방안을 제시하라는 문제이다.

 

코드

red, white, blue 각각 0 or 배열의 사이즈로 초기화 하고 각 원소의 초기 위치부터 swap 을 통해 정렬을 수행한다.

class Solution {
public:
    void sortColors(vector<int>& nums) {
        
        int red, white, blue;
        red = white = 0;
        blue = nums.size() - 1;
        
        while(white <= blue) {
            if(nums[white] == 0) {
                swap(nums[white], nums[red]);
                white++;
                red++;
            }
            else if(nums[white] == 2) {
                swap(nums[white], nums[blue]);
                blue--;
            }
            else {
                white++;
            }
        }
    }
};

 

map 을 이용한 풀이

class Solution {
public:
    void sortColors(vector<int>& nums) {

        // input 0, 1, 2 using counted sort
        int table[3] = { 0 };

        for (int i = 0; i < nums.size(); ++i) {
            table[nums[i]]++;
        }

        int index = 0;
        for (int i = 0; i < 3; ++i) {
            int cand = table[i];
            for (int j = 0; j < cand; ++j, ++index) {
                nums[index] = i;
            }
        }
    }
};

 

sort 를 이용한 풀이

class Solution {
public:
    void sortColors(vector<int>& nums) {
        
        sort(nums.begin(), nums.end());
    }
};