JavaScript로 인접 요소보다 큰 요소(피크 요소) 찾기

문제 정의

숫자 배열을 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.

이 함수는 배열에서 바로 왼쪽에 있는 숫자와 바로 오른쪽에 있는 숫자보다 모두 큰 요소를 찾아 반환해야 합니다. 이러한 조건을 만족하는 요소를 흔히 '피크(peak) 요소'라고 부릅니다. 만약 배열에 해당하는 요소가 여러 개 존재한다면, 그중 어떤 하나를 반환해도 무방합니다.

예를 들어 다음과 같은 입력 배열이 주어졌다고 가정해 보겠습니다.

const arr = [3, 6, 7, 9, 8, 2, 5];

이 경우 기대되는 출력은 다음과 같습니다.

const output = 9;

배열에서 9는 왼쪽의 7과 오른쪽의 8보다 크기 때문에 피크 요소의 조건을 충족합니다.

접근 방식: 이진 탐색 활용

이 문제는 본질적으로 피크 요소를 찾는 문제이므로, 이진 탐색(binary search) 알고리즘을 변형하여 효율적으로 해결할 수 있습니다. 단순히 배열을 처음부터 끝까지 순회하는 선형 탐색(O(n))과 달리, 이진 탐색을 활용하면 시간 복잡도 O(log n)으로 문제를 해결할 수 있습니다.

알고리즘의 핵심 단계는 다음과 같습니다.

탐색 범위의 중간에 있는 임의의 요소를 확인합니다.
현재 요소가 이전 요소와 다음 요소보다 모두 크다면, 바로 피크 요소를 찾은 것이므로 현재 요소를 반환합니다.
다음 요소가 현재 요소보다 크다면, 오른쪽 방향에 반드시 피크 요소가 존재하므로 오른쪽 절반을 재귀적으로 탐색합니다.
이전 요소가 현재 요소보다 크다면, 왼쪽 방향에 반드시 피크 요소가 존재하므로 왼쪽 절반을 재귀적으로 탐색합니다.

여기서 한 가지 중요한 포인트는 배열의 양 끝 경계를 처리하는 것입니다. 경계를 벗어나는 경우 -Infinity를 사용하면, 배열의 첫 번째나 마지막 요소가 피크인 경우에도 비교 로직이 자연스럽게 동작합니다.

구현 예제

다음은 위 알고리즘을 구현한 전체 코드입니다.

const arr = [3, 6, 7, 9, 8, 2, 5];

const greaterThanAdjacent = (arr = [], start = 0, end = arr.length - 1) => {
   // 탐색 범위의 중간 인덱스 계산
   let mid = start + Math.floor((end - start) / 2);
   
   // 현재 요소와 좌우 인접 요소 가져오기 (경계 처리 포함)
   let curr = arr[mid];
   let prev = mid - 1 < start ? -Infinity : arr[mid - 1];
   let next = mid + 1 > end ? -Infinity : arr[mid + 1];
   
   // 피크 요소 조건: 좌우보다 모두 클 때
   if (curr > prev && curr > next) {
      return arr[mid];
   }
   
   // 오른쪽에 피크가 존재하면 오른쪽 탐색
   if (curr < next) {
      return greaterThanAdjacent(arr, mid + 1, end);
   }
   
   // 왼쪽에 피크가 존재하면 왼쪽 탐색
   return greaterThanAdjacent(arr, start, mid - 1);
};

console.log(greaterThanAdjacent(arr));

실행 결과

위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.

동작 원리 살펴보기

예제 배열 [3, 6, 7, 9, 8, 2, 5]에서 알고리즘이 어떻게 동작하는지 단계별로 살펴보겠습니다.

초기 탐색 범위는 전체 배열이며, 중간 인덱스는 3입니다. 즉, 현재 요소는 arr[3] = 9입니다.
왼쪽 요소는 7, 오른쪽 요소는 8입니다. 9는 두 값보다 모두 크므로 즉시 피크 요소로 판별되어 반환됩니다.

운 좋게 첫 번째 시도에서 답을 찾았지만, 일반적인 경우에는 매 단계마다 탐색 범위가 절반으로 줄어들기 때문에 최악의 경우에도 O(log n)의 시간 안에 답을 찾을 수 있습니다.

마무리

이처럼 이진 탐색을 변형하면 정렬되지 않은 배열에서도 인접 요소보다 큰 피크 요소를 매우 효율적으로 찾을 수 있습니다. 핵심은 현재 위치의 좌우 값을 비교하여 어느 쪽에 피크가 존재하는지 판단하고, 탐색 범위를 절반씩 줄여 나가는 것입니다. 배열의 경계 처리를 위해 -Infinity를 활용하는 것도 깔끔한 구현을 위한 유용한 기법이니 기억해 두시기 바랍니다.