문제
오름차순으로 정렬된 정수 배열 arr을 입력받는 JavaScript 함수를 작성해야 합니다.
이 배열에는 전체 요소 수의 25%(1/4)보다 많이 등장하는 정수가 정확히 하나 존재하며, 함수는 바로 그 숫자를 반환해야 합니다.
예를 들어, 함수의 입력이 다음과 같다면 −
const arr = [3, 5, 5, 7, 7, 7, 7, 8, 9];
그렇다면 출력은 다음과 같아야 합니다 −
const output = 7;
접근 방법
배열이 이미 정렬되어 있으므로 처음부터 끝까지 모든 요소를 세는 선형 탐색 대신 이진 탐색(Binary Search)을 활용하면 훨씬 효율적으로 문제를 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다.
- 배열 길이의 1/4, 2/4, 3/4 지점에 있는 세 개의 값을 후보로 삼습니다. 어떤 값이 전체의 25% 이상 차지한다면, 이 세 지점 중 최소 한 곳에는 반드시 그 값이 존재하기 때문입니다.
- 각 후보 값에 대해 이진 탐색을 두 번 수행하여 가장 왼쪽 인덱스와 가장 오른쪽 인덱스를 구합니다.
- (오른쪽 인덱스 − 왼쪽 인덱스 + 1), 즉 등장 횟수가 배열 길이의 1/4보다 크면 해당 값이 정답입니다.
예제 코드
이 문제를 해결하는 코드는 다음과 같습니다 −
const arr = [3, 5, 5, 7, 7, 7, 7, 8, 9];
const oneFourthElement = (arr = []) => {
const len = arr.length / 4;
const search = (left, right, target, direction = 'left') => {
let index = -1
while (left <= right) {
const middle = Math.floor(left + (right - left) / 2);
if(arr[middle] === target){
index = middle;
if(direction === 'left'){
right = middle - 1;
}else{
left = middle + 1;
};
}else if(arr[middle] < target){
left = middle + 1;
}else{
right = middle - 1;
};
};
return index;
};
for(let i = 1; i <= 3; i++){
const index = Math.floor(len * i);
const num = arr[index];
const loIndex = search(0, index, num, 'left');
const hiIndex = search(index, arr.length - 1, num, 'right');
if(hiIndex - loIndex + 1 > len){
return num;
};
};
};
console.log(oneFourthElement(arr));
출력
콘솔에 출력되는 결과는 다음과 같습니다 −
7
복잡도 분석
시간 복잡도: O(log n) — 세 개의 후보 각각에 대해 두 번의 이진 탐색을 수행하지만, 이진 탐색 횟수가 상수이므로 전체 시간 복잡도는 O(log n)입니다.
공간 복잡도: O(1) — 추가적인 자료구조 없이 상수 공간만 사용하므로 메모리 측면에서도 매우 효율적입니다.