[자료구조와 알고리즘] 169. Majority Element (Feat. Boyer-Moore majority vote algorithm)

문제 설명

Leetcode Top Interview 150 - 169. Majority Element
n의 길이를 가진 배열 nums에서 과반수 이상 나오는 숫자를 반환하는 문제입니다.

풀어보기

문제에 가능하면 시간 복잡도가 O(N)이고 공간 복잡도가 O(1)인 방법으로 풀어보라는 follow-up이 붙어있어서 고민을 해봤습니다..만 공간 복잡도를 확실히 줄일 방법이 생각나지 않았습니다. 🥲

1. 객체 하나를 만들어서 { 숫자 : 나온 횟수 }로 카운팅하기

var majorityElement = function(nums) {
    const cnt = {}
    for (num of nums) {
        if (cnt[num] == undefined) {
            cnt[num] = 1;
        } else {
            cnt[num] += 1;
        }
        // 과반수를 넘기면 바로 반환하기!!
        if (cnt[num] > nums.length/2) return num    
    }
};

객체를 만들기때문에 공간을 차지해서 공간 복잡도에서 아쉬운 결과가 나왔습니다.

2. 일단 정렬해놓고 가운데 값 반환하기

var majorityElement = function(nums) {
    nums.sort();
    return nums[parseInt(nums.length/2)]
};

이 방법이 가독성도 좋고.. 통과는 되는데 nums의 요소가 3가지 이상이라면 문제를 해결하지 못할 것 같습니다.
그리고 sort함수를 사용해서 공간 복잡도를 별로 개선하지 못했습니다.

더 좋은 코드

follow-up 문제는 시간 복잡도가 O(N)이고 공간 복잡도가 상수 시간으로 유명한 보이어-무어 다수결 알고리즘을 사용하도록 유도한 문제였던 것 같습니다.

var majorityElement = function(nums) {
    let candidate;
    let count = 0;
    
    for (const num of nums) {
        if (count === 0) {
            candidate = num;
        }
        
        count += (num === candidate) ? 1 : -1
    }
    
    return candidate;
};

처음에는 이 코드를 바로 이해하지 못했었는데 보이어-무어 다수결 알고리즘을 사용한 코드였고
반환하는 값의 변수명을 candidate로 지은 이유도 따로 있었습니다.

Boyer–Moore majority vote algorithm

위의 그림과 코드를 같이 보면서 이해해보면 더 쉽습니다. x축을 candidate, y축을 count라고 보시면 됩니다.
기존 모양과 같다면 count가 올라가고, 새로운 모양이 나타나면 count가 내려가는 그래프입니다. 순서가 어느 정도 바뀐다고 해도 과반수인 candidate(🟥)는 마지막에 남아서 반환될 수 있습니다.
그런데 만약에 [🟥, 🟥, ⭐️, 🟥, ⭐️, 🔵, 🔵]순서라면 어떻게 될까요? 과반수가 아닌 🔵가 반환될 것입니다.
이 알고리즘은 복잡도에서는 강점을 갖지만 결과가 항상 과반수가 되지는 않을 수 있습니다.
그래서 이 알고리즘을 구현한 코드에서는 대부분 후보자 candidate라는 표현을 쓰고 있는 것을 발견할 수 있습니다.