[Leet code - 75] Sort Colors ✅

문제

Input : 정수 배열 nums가 주어진다. (각 원소의 종류는 {0, 1, 2}로 세 가지를 가진다)

Process : nums를 추가 공간 없이 정렬한다.

Output : X

 

※ 추가 공간 : 입력 크기에 영향을 받는 공간이라는 뜻, 상수 크기의 메모리는 가능하다.

예를들어 반복문에 사용되는 변수i 같은 경우, n이 몇이 됐던 4Byte를 가지는 O(1)의 공간이기 때문에 가능하다.

하지만 배열의 복사본은 n이 늘어남에 따라 같이 늘어나는 O(n)의 공간이기 때문에 불가능하다.

 

 

시간 복잡도

• $n$ = 300
• $n^2$ = 90'000 으로 통과 가능하다.

따라서, $O(n^2)$부터 고려해보면 된다.

 

 

해결 계획

n^2이 가능하기 때문에 버블,선택정렬을 자연스럽게 떠올렸고, 이 정렬은 추가 공간이 필요 없기 때문에 괜찮다고 생각했다.

하지만 더 빠른 방법이 있을 것 같아서 일단 차선책으로 생각해두었다.

 

n log n 단에서 알고있는 정렬은 퀵 정렬, 병합 정렬로,

병합 정렬만 추가 공간이 필요하지만 문제 풀 당시에는 퀵 까지 추가 공간이 필요한 줄 알고 제외했었다...

 

n 단에서 고민을 많이 해봤는데, 떠오른 아이디어가 어차피 원소의 종류가 3가지 밖에 없으니까,

순회하면서 값 하나에 대해서만 처리를 하는 식으로 하면 3n이 될 수도 있지 않을까? 해서 좀 더 깊게 고민했다.

 

그렇게 나온 아이디어가 0 ⇒ 1 ⇒ 2 순으로, 배열의 앞 부분부터 swap해 나가는 방식이다!

 

 

구현

실패 코드

void sortColors(vector<int>& nums) {
	
    // 정렬을 해야하는 idx, 정렬 완료 구간의 다음 idx를 가리킨다.
    int sortIdx = 0;
    
    // 0과 1만 정렬을 하면 2는 자동으로 정렬이 되어 있다.
    for(int sortNum = 0; sortNum < 2; ++sortNum)
    {
        // sortNum에 대해서만 swap 수행
        for (int i = sortIdx + 1; i < nums.size(); ++i)
        {
            if (nums[i] == sortNum) std::swap(nums[sortIdx++], nums[i]);
        }
    }
}

해당 코드를 실패하게 만든 예외 케이스가 존재했는데, 그 케이스는 바로 첫 부분이 어느정도 정렬된 케이스였다.

{0, 0, 1} 같은 경우 결과로 {1, 0, 0}이 되어버리고 만다.

 

문제의 원인은 sortIdx의 “정렬이 끝난 구간의 다음 인덱스”라는 불변식을 유지하지 못했기 때문이다.

첫 번째 루프에서 정렬할 값이 없으면 sortIdx가 이동하지 않는데,
이 상태에서 다음 루프가 시작되면서 이미 정렬된 값까지 다시 swap 대상이 되기 때문에 실패를 했었다.

 

즉, sortIdx 이전 구간은 항상 정렬되어 있어야 한다는 조건이 깨졌다.

통과 코드

그래서 스위치를 쓰니, 처음 만난 sortNum이외의 인덱스를 저장하니, 뭐니 해서 고민했지만,

다 너무 지저분하고 뭔가 나이스 하지 않았다..

 

그러다가 처음에 만나는 값들이 정렬이 되어 있다면, 정렬을 해야하는 인덱스까지 sortIdx를 옮기면 되겠다 라는 생각을 했고,

sortIdx에 대해 연산하는 총 횟수도 이전과 똑같기 때문에 안할 이유가 없었다.

 void sortColors(vector<int>& nums) 
 {
    int sortIdx = 0;
    
    for(int sortNum = 0; sortNum < 2; ++sortNum)
    {
        // 초기 sortIdx를 찾기
        while(sortIdx < nums.size() && nums[sortIdx] == sortNum) sortIdx++;

        for (int i = sortIdx + 1; i < nums.size(); ++i)
        {
            if (nums[i] == sortNum) std::swap(nums[sortIdx++], nums[i]);
        }
    }
}

 

 

되돌아보기

이번에 생각해본 정렬은 입력값의 개수가 아닌 입력값의 종류의 개수에 따라 복잡도가 늘어나기 때문에 뭔가 신기했다?

 

퀵 정렬은 in-place다

그리고 복잡도 계산할 때 잘못 생각한게 있었는데, 퀵 정렬도 in-place였다.. 하지만 완벽한 in-place는 아니다!

 

퀵 정렬은 재귀를 사용하기 때문에, 재귀 단계만큼의 스택 메모리가 따라오기 마련인데,

이미 정렬된 배열에 정렬을 시작했을 때 어떻게 보면 스택 메모리가 O(n)이 되기 때문이다.

 

근데 그래도 뭐 일단은 코테에서 in-place 정렬로 취급된다고 한다.!

 

퀵 정렬은 값의 종류가 3개뿐이라 비효율적?

찾아보면서 추가적으로 깨달은 건 데, 퀵 정렬은 범용적으로 사용 가능하지만 항상 최적은 아니라는 것이다.

특히 이번 문제는 퀵 정렬이 in-place가 아니라고 착각하지 않았다면 바로 퀵 정렬로 진행했을지도 모른다.

 

정렬은 어떻게 보면 계속 비교하는 알고리즘이다.

근데 이번 문제는 값이 0, 1, 2뿐이며, 정렬 기준도 오름차순 고정 이라는 명확한 정보도 알고 있기 때문에,

정렬보다는 분류에 가깝다고 할 수 있다.

 

 

그래서 해당 문제를 퀵 정렬로 풀어버린다면, 문제에서 준 정보를 활용하지 못한 선택이 된다.

 

 

개선 코드

진짜 내가 작성한 것보다 빠른 건 없을 듯 이라고 생각했지만, 역시나 똑똑한 사람은 많다...

Dutch National Flag 알고리즘

void sortColors(vector<int>& nums) {
    int low = 0, mid = 0, high = nums.size() - 1;

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

 

같은 아이디어서 시작하지만,

나는 앞으로만 보내는 방식으로 순회 3번을 하고, Dutch는 앞과 뒤로 보내면서 순회 1번으로 끝내버린다.

어떻게 보면 배열을 세 구간 (0 /1/ 2)를 동시에 유지하는 느낌이다.

 

근데 Dutch 알고리즘은 종류가 정확히 3개일 때 가장 효율적이다..!

종류가 더 많아지만 저장 인덱스도 많아지고 처리해야할 것도 선형적으로 늘어나기 때문에,

어떻게 보면 내가 작성한 코드가 조금 더 범용성 있을지도...모른다....(‾◡◝)