Problem

그냥은 풀 수 있겠지만 follow-up 문제는 풀 방법을 도저히 혼자서 생각해내지 못함...!
Problem: https://leetcode.com/problems/majority-element/

Approach

Boyer-Moore Voting Algorithm

The Boyer–Moore majority vote algorithm is an algorithm for finding the majority of a sequence of elements using linear time and constant space.

이 알고리즘을 알아야 O(n) time과 O(1) space 로 문제를 풀 수가 있었다!

1. Description

과반 수 이상을 차지하는 element는 다른 element들로 상쇄가 되지 않는다는 점을 이용한다.

위 예시 그림에서 x축이 element list, y축이 count이다. 과반 후보가 될 모양을 정하고, 그 후보가 또 나오면 +1, 나오지 않으면 -1 을 더해가다가 count가 0이 되는 경우 과반 후보를 바꾸어서 이어서 위 과정을 진행한다.
첫번째 후보는 첫 element인 파란 동그라미 였지만, +1 +1 -1 +1 -1 -1 을 거치며 count값이 0이 되어 후보가 노란 별로 교체되었다. 다시 같은 과정을 거치다가 빨간 네모가 나오면서 count 값이 0이 되어 후보가 빨간 네모가 되었고, 이후 해당 후보에 대해 count 값이 4에서 끝났다.
이로써 주어진 element list 에서 빨간 네모가 과반수 이상을 차지한다고 볼 수 있다!

출처: https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm

2. Time/Space Complexity

1) Time

모든 Element를 한번씩 훑어야 하므로, O(n) 시간이 소요된다

2) Space

O(1) 의 공간복잡도를 가진다