169.Majority Element

난이도: Easy

링크: LeetCode 169

풀이 날짜: 2025/10/15

 

1. 문제 이해

주어진 배열 nums에서 과반수 이상(배열 길이의 절반 이상) 등장하는 숫자를 찾는 문제다.

반드시 과반수 이상 존재한다고 가정하기 때문에, 한 값이 전체 배열의 절반 이상을 차지한다.

예) [3,2,3] → 3

예) [2,2,1,1,1,2,2] → 2

 

2. 접근 아이디어

이 문제의 효율적인 풀이로 Boyer-Moore Voting Algorithm을 사용할 수 있다.

 

Boyer-Moore Voting Algorithm

이 알고리즘은 배열을 한 번만 순회하면서 과반수 요소를 찾는 방법이다.

1. 후보값과 count를 관리
   • major라는 후보값을 하나 두고, 얼마나 지지받는지 count로 센다고 생각한다.
   • count가 0이면 후보값이 현재 숫자에 의해 “뒤집히는 순간”이라는 의미 → 이때 후보를 바꿔준다.
2. count를 +1 / -1로 조정
   • 현재 숫자가 후보값이면 지지 +1, 다르면 지지 -1
   • 배열을 순회하면서 후보값이 얼마나 “과반수로 우세한지” 체크
3. 왜 한 번만으로 되는가?
   • 문제 조건에서 반드시 과반수 요소가 존재
   • 어떤 수가 절반 이상이면, 다른 수들과 번갈아 나와도 결국 후보가 마지막까지 남음
   • 즉, count가 0으로 초기화되는 순간 후보를 바꿔도 최종적으로 과반수의 수가 최종 후보가 되는 것이다.

 

예시 시나리오

nums = [2, 2, 1, 1, 1, 2, 2] 

단계	현재 숫자	후보(candidate)	count	설명
1	2	2	1	후보가 없으므로 2로 설정, count = 1
2	2	2	2	같은 숫자이므로 count 증가
3	1	2	1	다른 숫자 → count 감소
4	1	2	0	다른 숫자 → count 감소 → 0이 되어 후보 초기화
5	1	1	1	후보가 없으므로 새 후보를 1로 설정
6	2	1	0	다른 숫자 → count 감소 → 0이 되어 후보 초기화
7	2	2	1	후보가 없으므로 새 후보를 2로 설정

최종 후보 = 2 → 실제로도 배열에서 2는 4번 등장 (전체 7개 중 과반수)

 

이처럼 count가 0이 될 때마다 후보를 교체하지만, 과반수 원소는 결국 “지워지지 않고 끝까지 살아남는 숫자”이다.

 

3. 풀이 코드

var majorityElement = function(nums) {
  let major = 0;   // 후보값
  let count = 0;   // 후보 카운트

  for(const num of nums) {
    if(count === 0) {
      major = num;    
    }
    count += major === num ? 1 : -1;
  }

  return major;
};

1. 후보값 갱신 - count가 0이면 현재 숫자를 새로운 후보로 설정
2. count 조정 - 현재 숫자가 후보값과 같으면 +1, 다르면 -1
3. 과반수 보장 - 과반수 이상 존재하기 때문에, 반복 후 후보값 major가 정답이 된다.

시간 복잡도는 배열을 한 번 순회하므로 O(n),

공간 복잡도는 추가 배열 없이 상수 변수만 사용하므로 O(1) 이다.

 

4. 정리

• Boyer-Moore Voting Algorithm 활용
• 한 번 순회로 과반수 요소를 찾을 수 있음
• 후보값과 카운트만 관리하면 되므로 공간 효율도 최고