C++로 정렬된 배열에서 n/2번 이상 등장하는 요소 찾기

크기가 n인 정렬된 배열이 있다고 가정해 봅시다. 이 배열에는 빈도(등장 횟수)가 n/2보다 크거나 같은 요소가 반드시 하나 존재합니다. 예를 들어 배열이 [3, 4, 5, 5, 5]라면, 5가 세 번 등장하므로 출력 결과는 5가 됩니다.

핵심 아이디어

이런 유형의 배열을 잘 관찰해 보면 매우 간단한 규칙을 발견할 수 있습니다. 정렬된 배열에서 n/2번 이상 등장하는 요소는 반드시 인덱스 n/2 위치에 존재한다는 것입니다.

그 이유는 다음과 같습니다. 어떤 값이 n개짜리 배열에서 최소 n/2번 등장하려면, 정렬된 상태에서 그 값들은 최소 길이 n/2짜리 연속된 구간을 형성해야 합니다. 길이 n인 배열에서 길이가 n/2 이상인 모든 연속 구간은 반드시 중앙 인덱스 n/2를 포함하게 됩니다. 따라서 배열 전체를 순회하며 개수를 셀 필요 없이, 단순히 arr[n/2] 값을 반환하기만 하면 됩니다.

예제 코드

#include<iostream>
using namespace std;

int higherFreq(int arr[], int n) {
    return arr[n / 2];
}

int main() {
    int arr[] = { 1, 2, 3, 4, 4, 4, 4, 4, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The number " << higherFreq(arr, n) 
         << " has occurred more than or equal to " << n 
         << "/2 amount of times";
    return 0;
}

실행 결과

The number 4 has occurred more than or equal to 10/2 amount of times

코드 설명

• higherFreq 함수는 배열과 배열의 크기를 인자로 받아 arr[n / 2] 값을 그대로 반환합니다.
• main 함수에서는 크기 10짜리 배열을 선언하고, sizeof(arr) / sizeof(arr[0])로 요소 개수를 계산한 뒤 결과를 출력합니다.
• 배열 {1, 2, 3, 4, 4, 4, 4, 4, 4, 5}에서 4는 여섯 번 등장하며, 이는 10/2 = 5보다 크므로 조건을 만족합니다.

시간 및 공간 복잡도

• 시간 복잡도: O(1) — 단일 인덱스 접근만 수행합니다.
• 공간 복잡도: O(1) — 추가 메모리가 필요하지 않습니다.

배열이 이미 정렬되어 있다는 전제 덕분에 해시 맵이나 카운팅 없이도 상수 시간에 답을 구할 수 있는 것이 이 문제의 핵심입니다.