JavaScript로 구현하는 합이 0에 가장 가까운 인접 요소 찾기

이번 글에서는 숫자 배열을 입력받아, 그중 합이 0(또는 목표값)에 가장 가까운 두 개의 인접 요소로 이루어진 부분 배열을 반환하는 JavaScript 함수를 만들어 보겠습니다.

만약 배열의 길이가 2보다 작다면, 비교할 쌍이 존재하지 않으므로 배열 전체를 그대로 반환하면 됩니다.

문제 예시

예를 들어 다음과 같은 배열이 주어졌다고 가정해 봅시다.

const arr = [4, 4, 12, 3, 3, 1, 5, -4, 2, 2];

위 배열에서 인접한 두 요소끼리의 합을 모두 살펴보면, [5, -4]의 합은 1로 어떤 인접 쌍보다도 0에 가장 가깝습니다. 따라서 함수는 [5, -4]를 반환해야 합니다.

해결 방법

이 문제는 배열을 한 번만 순회하며 각 인접 쌍의 합과 목표값 사이의 차이를 계산하는 방식으로 효율적으로 해결할 수 있습니다. 차이가 기존의 최솟값보다 작으면 해당 시작 인덱스와 차이 값을 갱신합니다.

코드

다음은 위 로직을 구현한 코드입니다.

const arr = [4, 4, 12, 3, 3, 1, 5, -4, 2, 2];

const closestElements = (arr, sum) => {
   // 배열 길이가 2 이하면 그대로 반환
   if(arr.length <= 2){
      return arr;
   }

   // reduce로 인접 쌍을 순회하며 최적의 조합 탐색
   const creds = arr.reduce((acc, val, ind) => {
      let { closest, startIndex } = acc;
      const next = arr[ind + 1];

      // 마지막 요소라면 더 이상 비교할 쌍이 없음
      if(!next){
         return acc;
      }

      // 목표값과 인접 쌍의 합 사이의 절대 차이 계산
      const diff = Math.abs(sum - (val + next));

      // 더 가까운 쌍을 발견하면 갱신
      if(diff < closest){
         startIndex = ind;
         closest = diff;
      }

      return { startIndex, closest };
   }, {
      closest: Infinity,
      startIndex: -1
   });

   const { startIndex: s } = creds;
   return [arr[s], arr[s + 1]];
};

console.log(closestElements(arr, 1));

실행 결과

콘솔에서 확인할 수 있는 출력 결과는 다음과 같습니다.

[5, -4]

정리

이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다. reduce 메서드와 누적 객체를 활용하면 반복문 없이도 깔끔하게 최적의 인접 쌍을 찾을 수 있으며, 목표값을 자유롭게 변경할 수 있어 다양한 상황에 재사용 가능한 함수입니다.