[LeetCode] 75. Sort Colors

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

Sort Colors - LeetCode

Sort Colors - Medium

 

0과 1과 2만 있는 배열 nums를 sort 라이브러리를 사용하지 않고 in-place로 정렬하는 문제다.

0의 개수와 2의 개수만 저장해놓으면 쉽게 풀이할 수 있다.

배열의 결과는 [0,0,...,0(0의 개수만큼), 1,1,...,1, 2, 2,...2(2의 개수만큼)] 와 같이 될 것이다.

 

0의 개수를 w = 0으로,

2의 개수를 배열사이즈-1-b = 0 로 세팅하자. (즉, b = 배열 사이즈 -1)

 

그 뒤, 배열을 앞에서 부터 훑으며 0일 경우, nums[i] 와 nums[w] 를 바꿔준다.

=> 현재 수 이전까지 0의 개수에 해당하는 인덱스와 바꿔준다. 그럼 앞에는 0만 채워질 것이다.

그리고 i와 w를 ++ 해준다.

 

1일 경우, i를 ++ 해준다.

 

2일 경우, nums[i]와 nums[b] 를 바꿔주고, b만 -- 해준다.

=> i++을 안해주는 이유는, nums[b]가 0일 경우, 이를 다시 앞으로 보내야하는데 그렇지 않고 넘어가기 때문에 한번더 체크를 해줘야 한다.

 

전체 풀이 코드

class Solution {
public:
    void sortColors(vector<int>& nums) {
        for (int i=0, w=0, b=nums.size()-1; i<=b;) {
            if (nums[i]==0) swap(nums[i++], nums[w++]);
            else if (nums[i]==2) swap(nums[i], nums[b--]);
            else i++;
        }
    }
};