정렬된 배열이 주어졌을 때, 특정 숫자 x가 해당 배열의 과반수(majority) 요소인지 판별하는 문제를 살펴보겠습니다.
여기서 과반수 요소란 배열 전체 길이 n의 절반, 즉 n/2번보다 많이 등장하는 요소를 의미합니다.
문제 이해하기
예를 들어 배열이 {1, 2, 3, 3, 3, 3, 6}이고 x = 3이라고 가정해 봅시다. 숫자 3은 총 4번 등장하고, 배열의 크기는 7이므로 4 > 7/2(=3.5)를 만족합니다. 따라서 3은 과반수 요소이며 결과는 true가 됩니다.
만약 x = 6이라면 6은 한 번만 등장하므로 과반수 요소가 아니며 결과는 false입니다.
접근 방법: 빈도 수 직접 세기
가장 간단한 방법은 배열을 순회하면서 x의 등장 횟수를 세는 것입니다. 배열이 오름차순으로 정렬되어 있으므로, 현재 요소가 x보다 커지는 순간 반복문을 조기 종료하면 불필요한 탐색을 줄일 수 있습니다. 최종적으로 개수가 n/2보다 크면 true, 그렇지 않으면 false를 반환합니다.
C++ 구현 예제
#include <iostream>
#include <stack>
using namespace std;
bool isMajorityElement(int arr[], int n, int x){
int freq = 0;
for(int i = 0; i<n; i++){
if(arr[i] == x)
freq++;
if(arr[i] > x)
break; // 정렬된 배열이므로 x 이후는 더 볼 필요 없음
}
return (freq > n/2);
}
int main() {
int arr[] = {1, 2, 3, 3, 3, 3, 6};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 3;
if (isMajorityElement(arr, n, x))
cout << x << " 는 배열의 과반수 요소입니다";
else
cout << x << " 는 배열의 과반수 요소가 아닙니다";
}실행 결과
3 는 배열의 과반수 요소입니다
더 효율적인 방법: 이진 탐색 활용
위 방법의 시간 복잡도는 O(n)입니다. 하지만 배열이 이미 정렬되어 있다는 점을 활용하면 이진 탐색(binary search)으로 성능을 개선할 수 있습니다.
C++ STL의 lower_bound(x가 처음 등장하는 위치)와 upper_bound(x보다 처음 커지는 위치)를 사용하면 x의 등장 횟수를 O(log n) 시간에 구할 수 있습니다.
#include <iostream>
#include <algorithm>
using namespace std;
bool isMajorityElement(int arr[], int n, int x){
int first = lower_bound(arr, arr + n, x) - arr;
int last = upper_bound(arr, arr + n, x) - arr;
return (last - first) > n / 2;
}복잡도 비교
- 선형 탐색: 시간 복잡도 O(n), 공간 복잡도 O(1)
- 이진 탐색: 시간 복잡도 O(log n), 공간 복잡도 O(1)
배열이 정렬되어 있는 경우에는 이진 탐색 기반 접근이 훨씬 효율적이므로, 실무에서는 lower_bound와 upper_bound를 활용한 방법을 권장합니다.