Majority Element

길이가 n인 배열에서 과반수(Majority Element), 즉 $\lfloor n / 2 \rfloor$ 번을 초과하여 등장하는 원소를 찾는 문제다. 문제 조건에서 과반수 원소는 항상 존재한다고 보장된다.

가장 먼저 떠오르는 방법은 두 가지다.

해시 맵(Hash Map)으로 등장 횟수 카운팅: 배열을 순회하며 빈도를 기록하고 $\lfloor n / 2 \rfloor$ 보다 큰 원소를 찾는다. $\to$ 시간 $O(n)$ , 공간 $O(n)$
정렬(Sorting): 배열을 정렬하면 과반수를 차지하는 원소는 반드시 가운데 인덱스 nums[Math.floor(n / 2)]에 위치한다. $\to$ 시간 $O(n \log n)$ , 공간 $O(1)$ 또는 $O(n)$

하지만 문제의 Follow-up 조건은 다음과 같다.

시간 복잡도 $O(n)$ , 추가 공간 복잡도 $O(1)$ 로 해결할 수 있는가?

모든 원소의 개수를 일일이 세지 않고( $O(1)$ 공간), 정렬도 하지 않으면서( $O(n)$ 시간) 어떻게 과반수 원소를 찾아낼 수 있을까?

핵심 아이디어: 서로 다른 두 원소의 1:1 상쇄

질문을 바꾸어보자.

“모든 원소의 정확한 개수를 알 필요가 있는가? 과반수를 넘는 단 하나의 원소만 찾으면 되는 것 아닌가?”

과반수 원소(Majority Element)의 정의는 전체의 절반을 초과( $> n / 2$ )하는 원소다.

이 정의에서 매우 강력한 성질이 유도된다.

“서로 다른 원소 2개를 짝지어 함께 제거(상쇄)하더라도, 과반수 원소는 여전히 과반수를 유지하거나 마지막까지 살아남는다.”

예를 들어, 7명 중 4명이 찬성(A)이고 3명이 반대(B)라고 하자.

A A A A B B B

찬성표 1개와 반대표 1개를 묶어서 동시에 소거해 본다.

(A, B) 소거 → 남은 표: A A A B B
(A, B) 소거 → 남은 표: A A B
(A, B) 소거 → 남은 표: A (최종 생존)

반대표(비과반수)가 모두 단결하여 찬성표(과반수)를 하나씩 물고 늘어져 함께 탈락하더라도, 과반수 원소는 전체의 절반을 초과하므로 반드시 1개 이상 남아 최종 승자가 된다.

이 원리를 바탕으로 고안된 알고리즘이 바로 **보이어-무어 과반수 투표 알고리즘(Boyer-Moore Voting Algorithm)**이다.

Boyer-Moore Voting Algorithm의 작동 원리

이 알고리즘은 단 2개의 변수만 사용한다.

candidate: 현재 살아남아 있는 과반수 후보
count: 현재 후보의 “순 잉여 득표수” (다른 원소와 상쇄되고 남은 수량)

배열을 왼쪽에서 오른쪽으로 순회하면서 다음 규칙에 따라 상태를 갱신한다.

1. count가 0이면:
   현재 원소를 새로운 candidate로 지정하고 count를 1로 설정한다.

2. 현재 원소가 candidate와 같으면:
   count를 1 증가시킨다 (지지표 획득).

3. 현재 원소가 candidate와 다르면:
   count를 1 감소시킨다 (서로 다른 원소끼리 1:1 상쇄).

왜 `count === 0`일 때 후보를 바꿔도 안전할까?

count가 0이 되었다는 것은, 지금까지 지나온 구간에서 등장한 원소들이 서로 상쇄되어 완전히 소거되었음을 의미한다.

지나온 부분 배열에서 과반수 원소가 일부 소거되었더라도, 함께 소거된 비과반수 원소의 수가 같거나 더 많기 때문에 아직 탐색하지 않은 나머지 배열에서도 원래의 과반수 원소는 여전히 과반수(또는 최대 다수)의 지위를 유지한다.

따라서 count === 0이 되는 순간, 앞선 구간은 깨끗이 잊고 현재 위치부터 새로운 부분 배열로 보고 투표를 다시 시작할 수 있다.

자연어 알고리즘

candidate를 nums[0](또는 0), count를 0으로 초기화한다.
배열의 각 원소 num을 순회한다.
- count가 0이면, 현재 num을 candidate로 지정한다.
- num === candidate이면 count를 1 증가시킨다.
- num !== candidate이면 count를 1 감소시킨다.
순회가 끝나면 최종 candidate를 반환한다.

TypeScript 구현

function majorityElement(nums: number[]): number {
  let candidate = nums[0];
  let count = 0;

  for (const num of nums) {
    if (count === 0) {
      candidate = num;
    }

    count += num === candidate ? 1 : -1;
  }

  return candidate;
}

복잡도 분석

시간 복잡도: $O(n)$
배열을 한 번만 선형 순회하므로 원소의 개수에 비례하는 시간이 소요된다.
공간 복잡도: $O(1)$
candidate와 count라는 2개의 원시 변수만 사용하므로 추가 메모리를 전혀 사용하지 않는다.

핵심 인사이트

1. “전체 상태 기록”에서 “상대적 차이 추적”으로

모든 숫자의 출현 횟수를 구하려면 해시 맵( $O(n)$ 공간)이 필요하다. 하지만 우리가 원하는 것은 모든 숫자의 분포가 아니라, 절반을 넘는 단 하나의 원소다.

Boyer-Moore 알고리즘은 각 숫자의 절대적인 빈도를 세는 대신, **후보 원소와 비후보 원소 간의 상대적인 차이(Net Advantage)**만을 $O(1)$ 공간에서 추적한다.

2. 1:1 상쇄 불변식 (Pairwise Elimination Invariant)

어떤 원소가 전체의 $> n/2$ 를 차지한다면, 나머지 모든 원소가 연합하여 1:1로 함께 탈락하는 최악의 시나리오에서도 과반수 원소의 개수가 더 많기 때문에 무조건 살아남는다.

3. 과반수 원소가 항상 존재한다는 전제

이 알고리즘은 **“과반수 원소가 반드시 존재한다”**는 문제 조건이 있을 때 한 번의 순회( $O(n)$ )로 유효하다. 만약 과반수 원소가 존재하지 않을 수도 있는 일반적인 상황이라면, 알고리즘 종료 후 찾은 candidate의 실제 등장 횟수가 $\lfloor n / 2 \rfloor$ 를 넘는지 검증하는 2차 순회 단계( $O(n)$ )를 한 번 더 거치면 된다.