문제 개요
정렬된 배열이 하나 주어져 있다고 가정해 봅시다. 우리가 해야 할 일은 주어진 숫자 x가 해당 배열의 과반수 요소(majority element)인지 판별하는 것입니다.
여기서 과반수 요소란 배열 전체 길이의 절반(n/2)보다 많이 등장하는 원소를 의미합니다. 예를 들어 배열이 {1, 2, 3, 3, 3, 3, 6}이고 x = 3이라면 답은 true입니다. 배열 안에 3이 네 번 등장하고, 배열의 크기는 7이므로 4 > 7/2 조건을 만족하기 때문입니다.
접근 방법
가장 직관적인 방법은 배열을 한 번 순회하면서 x의 등장 횟수를 세는 것입니다. 개수가 n/2보다 크면 true를, 그렇지 않으면 false를 반환하면 됩니다.
배열이 이미 정렬되어 있다는 점을 활용하면 더 효율적으로 만들 수 있습니다. 순회 중 arr[i]가 x보다 커지는 순간 이후에는 x가 다시 등장할 수 없으므로, 반복을 즉시 종료하면 불필요한 비교를 줄일 수 있습니다.
알고리즘 단계
- 등장 횟수를 저장할 변수 freq를 0으로 초기화합니다.
- 배열을 처음부터 끝까지 순회하며 arr[i] == x이면 freq를 1 증가시킵니다.
- arr[i] > x가 되면 반복을 종료합니다(정렬된 배열이므로 이후에 x는 존재하지 않음).
- freq > n/2 여부를 반환합니다.
C++ 구현 예제
#include <iostream>
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;
}
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 << " 는 배열의 과반수 요소가 아닙니다";
}입력
[1, 2, 3, 3, 3, 3, 6]
3
출력
3 는 배열의 과반수 요소입니다
복잡도 분석
- 시간 복잡도: O(n) — 최악의 경우 배열 전체를 한 번 순회합니다.
- 공간 복잡도: O(1) — 추가 메모리를 거의 사용하지 않습니다.
개선 아이디어: 이진 탐색 활용
배열이 정렬되어 있으므로 이진 탐색을 사용하면 시간 복잡도를 O(log n)까지 줄일 수 있습니다. C++ STL의 lower_bound와 upper_bound를 이용해 x가 처음 등장하는 위치와 마지막으로 등장한 다음 위치를 찾은 뒤, 두 위치의 차이가 n/2보다 큰지 확인하면 됩니다.
#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;
}이처럼 정렬된 배열의 특성을 활용하면 단순 선형 탐색보다 훨씬 빠르게 과반수 요소 여부를 판별할 수 있습니다.