n개의 원소를 가진 정렬된 배열이 있다고 가정해 보겠습니다. 이 배열 안에서 어떤 원소를 기준으로 그보다 작은 원소의 개수와 큰 원소의 개수가 정확히 같은 지점(Equal Point)이 존재하는지 찾아야 합니다. 만약 이러한 지점이 여러 곳에 나타난다면 첫 번째로 등장하는 위치의 인덱스를 반환하고, 존재하지 않는다면 -1을 반환합니다.
예를 들어 A = [1, 1, 2, 3, 3, 3, 3, 3]이라는 배열이 있다면, Equal Point는 인덱스 2에 위치하며 해당 원소는 A[2] = 2입니다. 2보다 작은 원소는 1 하나뿐이고, 2보다 큰 원소 역시 3 하나뿐이기 때문입니다.
접근 방법
이 문제는 보조 배열(auxiliary array)을 활용해 효율적으로 해결할 수 있습니다. 먼저 배열에서 중복을 제거하고, 서로 다른(distinct) 원소가 시작되는 지점의 인덱스만 보조 배열에 저장합니다. 이후 distinct 원소의 개수를 확인하여 답을 결정합니다.
- distinct 원소의 개수가 짝수라면: 좌우 원소 개수가 동일한 중간 지점이 존재할 수 없으므로 -1을 반환합니다.
- distinct 원소의 개수가 홀수라면: 보조 배열의 정중앙에 있는 원소가 바로 Equal Point가 됩니다.
예제 코드 (C++)
#include<iostream>
using namespace std;
int searchEqualPoint(int arr[], int n) {
int aux_arr[n];
int i = 0, aux_index = 0;
while (i < n) {
aux_arr[aux_index++] = i++;
while (i < n && arr[i] == arr[i-1])
i++;
}
return (aux_index & 1) ? aux_arr[aux_index >> 1] : -1;
}
int main() {
int arr[] = {1, 1, 2, 3, 3, 3, 3, 3};
int n = sizeof(arr)/sizeof(arr[0]);
int index = searchEqualPoint(arr, n);
if (index != -1)
cout << "Equal Point is: " << arr[index];
else
cout << "No Equal Point exists";
}
실행 결과
Equal Point is: 2
동작 원리 및 복잡도
내부의 while 루프는 현재 원소와 이전 원소가 같은 동안 인덱스를 계속 건너뛰어 중복을 제거하고, 각 distinct 값이 처음 등장하는 인덱스만 aux_arr에 저장합니다. 마지막으로 distinct 원소의 개수(aux_index)가 홀수인지 비트 연산(& 1)으로 확인하고, 홀수라면 aux_index >> 1(절반 위치, 즉 중앙)에 해당하는 원래 배열의 인덱스를 반환합니다.
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 보조 배열을 사용하기 때문에 공간 복잡도 역시 O(n)입니다. 배열이 이미 정렬되어 있다는 전제 조건만 충족되면 중복이 많은 대용량 데이터에서도 빠르게 균형점을 찾을 수 있습니다.