문제 개요
정수 배열이 하나 주어졌을 때, n/3번(내림 값)보다 많이 등장하는 모든 원소를 찾아야 합니다. 여기서 n은 배열의 크기를 의미합니다.
예를 들어 입력 배열이 [1,1,1,3,3,2,2,2]라고 가정해 보겠습니다. 배열의 크기 n은 8이므로 8/3 = 2, 즉 2번보다 많이 등장하는 원소를 찾으면 됩니다. 이 경우 1은 세 번, 2는 세 번 등장하므로 결과는 [1, 2]가 됩니다.
접근 방법: 보이어-무어(Boyer-Moore) 다수결 투표 알고리즘
n/3보다 많이 등장하는 원소는 최대 2개까지만 존재할 수 있습니다. 만약 후보가 3개 이상이라면 각각 n/3번보다 많이 등장해야 하므로 전체 등장 횟수가 3 × (n/3) = n을 초과하게 되어 모순이 발생하기 때문입니다. 따라서 후보 원소를 두 개만 유지하면서 카운트를 조정하는 방식으로 문제를 해결할 수 있습니다.
알고리즘 단계
- first := 0, second := 1, cnt1 := 0, cnt2 := 0으로 초기화하고, n은 배열 nums의 크기로 설정합니다.
- i를 0부터 n-1까지 반복합니다.
- x := nums[i]
- x가 first와 같으면 cnt1을 1 증가시킵니다.
- 그렇지 않고 x가 second와 같으면 cnt2를 1 증가시킵니다.
- 그렇지 않고 cnt1이 0이면 first를 x로 설정하고 cnt1 := 1로 합니다.
- 그렇지 않고 cnt2가 0이면 second를 x로 설정하고 cnt2 := 1로 합니다.
- 위 어느 경우에도 해당하지 않으면 cnt1과 cnt2를 각각 1씩 감소시킵니다.
- 검증을 위해 cnt1 := 0, cnt2 := 0으로 다시 초기화합니다.
- i를 0부터 n-1까지 반복하며 실제 등장 횟수를 셉니다.
- nums[i]가 first와 같으면 cnt1을 1 증가시키고, 그렇지 않고 nums[i]가 second와 같으면 cnt2를 1 증가시킵니다.
- 결과를 담을 배열 ret을 생성합니다.
- cnt1 > n/3이면 first를 ret에 삽입합니다.
- cnt2 > n/3이면 second를 ret에 삽입합니다.
- ret을 반환합니다.
두 번째 검증 단계가 필요한 이유는 첫 번째 패스에서 선택된 first와 second는 어디까지나 '후보'일 뿐, 실제로 n/3보다 많이 등장한다는 보장이 없기 때문입니다. 실제 등장 횟수를 직접 세어 조건을 확인해야 정확한 답을 얻을 수 있습니다.
C++ 구현 예제
다음 구현을 통해 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int first = 0;
int second = 1;
int cnt1 = 0;
int cnt2 = 0;
int n = nums.size();
for(int i = 0; i < n; i++){
int x = nums[i];
if(x == first){
cnt1++;
}
else if(x == second){
cnt2++;
}
else if(cnt1 == 0){
first = x;
cnt1 = 1;
}
else if(cnt2 == 0){
second = x;
cnt2 = 1;
} else {
cnt1--;
cnt2--;
}
}
cnt1 = 0;
cnt2 = 0;
for(int i = 0; i < n; i++){
if(nums[i] == first)cnt1++;
else if(nums[i] == second)cnt2++;
}
vector <int> ret;
if(cnt1 > n / 3)ret.push_back(first);
if(cnt2 > n / 3)ret.push_back(second);
return ret;
}
};
main(){
Solution ob;
vector<int> v = {1, 1, 1, 3, 3, 2, 2, 2};
print_vector(ob.majorityElement(v));
}입력
[1,1,1,3,3,2,2,2]
출력
[2, 1]
복잡도 분석
이 알고리즘은 배열을 두 번 순회하므로 시간 복잡도는 O(n)이며, 추가 공간은 상수 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다. 해시 맵을 사용해 각 원소의 빈도를 세는 방식(O(n) 시간, O(n) 공간)보다 메모리 측면에서 효율적이라는 장점이 있습니다.