JavaScript 이진 탐색으로 타겟보다 큰 가장 작은 문자 찾기

문제 설명

소문자로만 구성되어 있고 오름차순으로 정렬된 문자 배열 letters와 목표 문자 target이 주어졌다고 가정해 봅시다.

우리는 배열을 첫 번째 인수로, 목표 문자를 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 배열에서 목표 문자보다 큰 요소 중 가장 작은 것을 찾아 반환해야 합니다.

여기서 중요한 점은 문자가 순환(wrap around)한다는 것입니다. 즉, 목표가 'z'이고 배열이 ['a', 'b']라면 'z'보다 큰 문자가 존재하지 않으므로 다시 처음으로 돌아가 답은 'a'가 됩니다.

예시

입력 배열과 목표 문자가 다음과 같다면 −

const arr = ["c", "f", "j"];
const target = "a";

출력은 다음과 같아야 합니다 −

const output = "c";

'a'보다 큰 문자 중 가장 작은 것이 'c'이기 때문입니다.

접근 방식: 이진 탐색 활용

배열이 이미 정렬되어 있으므로 이진 탐색(binary search)을 사용하면 O(log n)의 시간 복잡도로 문제를 효율적으로 해결할 수 있습니다. 처음부터 끝까지 하나씩 확인하는 선형 탐색(O(n))보다 훨씬 빠른 방법입니다.

탐색 과정은 다음과 같습니다.

중간 지점의 문자가 목표보다 작거나 같으면, 조건을 만족하는 값은 오른쪽 절반에 있으므로 탐색 범위를 오른쪽으로 좁힙니다.
중간 지점의 문자가 목표보다 크면, 해당 위치가 정답 후보가 될 수 있으므로 현재 위치를 포함한 왼쪽 절반으로 범위를 좁힙니다.
탐색이 끝난 후 최종 위치의 문자가 목표보다 크지 않다면, 즉 모든 문자가 목표 이하라면 순환 규칙에 따라 배열의 첫 번째 문자를 반환합니다.

구현 코드

이에 대한 전체 코드는 다음과 같습니다 −

const arr = ["c", "f", "j"];
const target = "a";

const findNearestLetter = (arr = [], target = '') => {
   let left = 0;
   let right = arr.length - 1;

   while (left < right) {
      const mid = Math.floor((left + right) / 2);
      if (arr[mid] <= target) {
         left = mid + 1;
      } else {
         right = mid;
      }
   }

   // 모든 문자가 target 이하일 경우 순환하여 첫 번째 문자 반환
   return arr[left] > target ? arr[left] : arr[0];
};

console.log(findNearestLetter(arr, target));

출력 결과

콘솔 출력 결과는 다음과 같습니다 −

복잡도 분석

시간 복잡도: O(log n) — 매 반복마다 탐색 범위가 절반으로 줄어듭니다.
공간 복잡도: O(1) — 추가적인 메모리를 사용하지 않습니다.