[LeetCode] 75. Sort Colors

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

leetcode - Sort Colors

문제 유형 : 정렬

문제 난이도 : Medium

 

문제

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.

 

배열 nums가 주어진다. red, white, blue의 값을 가지고, 각각 0,1,2의 정수이다.

in-place의 정렬을 해서 red-white-blue순으로 오게 하라.

 

라이브러리의 sort함수를 사용하지 말고 해결하시오.

 

풀이

in-place의 정렬을 하기 위해, 상수 공간만을 사용하여야 한다.

정수 left, right, mid를 만든다.각각 0, n-1, 0으로 초기화한다.

 

mid가 right보다 작거나 같은동안 다음을 실행한다:

만약 nums[mid]가 0이면, left와 mid를 바꾸고, left와 mid를 1 증가한다.

만약 nums[mid]가 1이면, mid를 1증가한다.

만약 nums[mid]가 2이면, mid와 right을 바꾸고, right을 1 감소한다.

 

 

코드

C++

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int left = 0;
        int right = nums.size()-1;
        int mid = 0;

        while(mid <= right) {
            if(nums[mid] == 0) {
                swap(nums[left], nums[mid]);
                left++;
                mid++;
            } else if(nums[mid] == 1) {
                mid++;
            } else {
                swap(nums[mid], nums[right]);
                right--;
            }
        }
    }
};