문제
int 배열에서 가장 자주 등장하는 원소의 값을 리턴하는 문제
arraySize / 2 값보다 자주 등장하는 원소가 있다고 가정한다.
최초 풀이법
가장 쉬우나, 비효율적인 풀이 방법
map을 사용해서 <배열의 값, 등장 횟수> 를 저장하고, 가장 자주 나온 값을 매번 갱신하면서 가장 자주 나온 값을 반환하도록 풀었다.
import java.util.HashMap;
import java.util.Map;
class Solution {
public int majorityElement(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
int maxValue = 1, maxKey = nums[0];
for (int num : nums) {
if (map.containsKey(num)) {
int value = map.get(num) + 1;
if (value > maxValue) {
maxValue = value;
maxKey = num;
}
map.put(num, value);
} else {
map.put(num, 1);
}
}
return maxKey;
}
}
그런데 이 풀이는 너무 비효율적이다
맵으로 모든 값을 다 들고있어야 하고, 매번 key가 있는지 조회 + 값 update + max값을 찾기 위한 연산 등
개선한 풀이법
Boyer–Moore 알고리즘 활용
Boyer–Moore Voting Algorithm("과반수 투표 알고리즘") 이란?
"과반(> n/2) 원소가 존재할 때" 이를 O(n) 시간, O(1) 공간으로 찾는 방법입니다.
핵심은 “서로 다른 값은 1:1로 상쇄(cancellation)된다”는 관찰입니다.
가장 많이 나오는 원소가 전체 배열의 반 이상 들어있다(Majority)는 점에 주목하여
다른 원소와 상쇄하면서 가장 마지막까지 남아있는 원소를 찾는다.
추가적인 메모리를 사용하지 않고, map get, update등의 연산이 없기 때문에 간단하다.
class Solution {
public int majorityElement(int[] nums) {
int count = 0, candidate = 0;
for (int num : nums) {
if (count == 0) {
candidate = num;
count = 1;
} else if (candidate == num) {
count++;
} else {
count--;
}
}
return candidate;
}
}
Q1.
가장 많이 나오는 원소가 전체 배열의 반 이상 들어있다(Majority) 라는 조건이 없다면, 이 코드에서 얻은 candidate가 배열의 최빈값 (가장 자주 등장하는 값)이라고 말할 수 있는가?
A1.
아니다. 과반수가 넘지 않을 경우, candidate가 최빈값임을 보장할 수 없다.
예시) {1,2,3,1} 일 경우, 처음에 1과 2가 상쇄되고, 3과 1이 상쇄되나 3이 candidate인 채로 끝난다. 그러나 이 예시에서 최빈값은 1이다.
만약 과반수가 넘을 경우 {1,2,3,1,1} 이라면, 처음에 1과 2가 상쇄되고, 3과 1이 상쇄되나 마지막에 다시 1이 결국 candidate가 된다. 그래서 candidate 값이 최빈값임을 보장할 수 있다.
왜 과반이 넘는다면 최빈값이라고 보장할 수 있는가? (불변식 관점)
처리한 prefix(앞부분)에 대해 count는 대략 다음 의미를 가집니다.
현재 candidate의 등장 횟수 − (candidate가 아닌 값들의 “상쇄에 사용된” 횟수)
즉, 알고리즘은 “후보 vs 비후보”를 계속 페어링해서 제거하고 있고, 과반 원소 M이 있다면:
- 전체에서 M의 개수는 > n/2
- 나머지(비-M)의 개수는 < n/2
- M은 비-M과 최대 1:1로만 상쇄될 수 있으므로 M이 남을 수밖에 없음
그래서 “과반 존재” 조건이 붙으면 결과를 그대로 반환해도 됩니다.
때문에, 과반이 아닐 경우 해당 값이 정말 최빈값인지 검증하기 위한 로직이 필요하다.
Q2.
그렇다면, 과반이 아닌 상황에서 나온 값이 최빈값은 아니라 할지라도, 제일 많이 등장한 값 중 하나이지 않을까?
(즉, 크기가 5인 배열에서 2개씩 등장하는 수가 2개라면 그중 하나이지 않을까?)
A2.
아니다, 위의 {1,2,3,1} 예시를 보면 알 수 있듯이, 1이 최빈값이나 candidate 값은 3이 나온다.
과반이 아닌 상황에서의 candidate는 끝까지 남은 값일 뿐 최빈값임을 보장할 수 없다.
입력 순서에 따라 최빈값이 탈락하고, 상대적으로 덜 나온 값이 마지막에 남을 수 있다.
총평
| 시간복잡도 | 공간복잡도 | |
| 첫 풀이 (hashmap 사용) | O(n) | O(n) |
| 두번째 풀이 (Boyer–Moore Voting) | O(n) 동일한 O(n)이나 두번째 풀이가 훨씬 빠름 |
O(1) |
by GPT, 시간/공간복잡도 자세히 보기
1) 시간 복잡도 (Time Complexity)
A. HashMap 카운팅
- Big-O: 평균 O(n)
- 각 원소마다 containsKey/get/put을 수행하므로 원소당 평균 O(1) 해시 연산이 누적됩니다.
- 단, 이론적으로는 해시 충돌이 매우 심하거나(병목) 최악의 경우 O(n^2)까지 갈 수 있지만, 자바의 일반적인 HashMap 사용에서는 보통 **평균 O(n)**으로 봅니다.
실제 성능 관점
- 해시 연산(해시 계산, 버킷 탐색), 오토박싱(int → Integer), 객체 접근 등 오버헤드가 있어 상수항이 큽니다.
- 하지만 여전히 충분히 빠른 편이며, n=5e4 정도에서는 대개 문제 없이 통과합니다.
B. Boyer–Moore Voting
- Big-O: O(n)
- 원소당 비교 몇 번 + count 증감만 수행(정수 연산 중심).
- 최악/평균 구분 없이 깔끔하게 선형입니다.
실제 성능 관점
- 매우 작은 상수항(해시/박싱 없음).
- 같은 O(n)이라도 보통은 Boyer–Moore가 더 빠르게 나오는 경우가 많습니다.
2) 공간 복잡도 (Space Complexity)
A. HashMap 카운팅
- Big-O: O(k) (k = 서로 다른 값의 개수, 최악 k = n → O(n))
- 배열에 값이 다양하게 섞이면 map 엔트리가 많이 쌓입니다.
실제 메모리 관점(중요)
- HashMap<Integer, Integer>는 primitive가 아니라 객체 기반이라:
- 키/값 Integer 객체(오토박싱)
- HashMap 내부 Node(엔트리) 객체/구조
- 리사이징에 따른 추가 버킷 배열
등으로 메모리 오버헤드가 큽니다.
- 즉, Big-O 상 O(n)일 뿐 아니라 상수항이 매우 큰 O(n) 입니다.
B. Boyer–Moore Voting
- Big-O: O(1)
- candidate, count 두 개의 int만 사용합니다.
- 입력 크기와 무관하게 추가 메모리 사용량이 일정합니다.
easy 문제라서 가볍게 봤는데, 보면서 다양한 접근을 해볼 수 있는 문제였다.
재밌었음. 끝!
댓글