JavaScript 배열에서 목표 합계에 가장 가까운 두 숫자 쌍 찾기

이번 튜토리얼에서는 첫 번째 인자로 숫자 배열을, 두 번째 인자로 목표 숫자 하나를 받는 JavaScript 함수를 작성하는 방법을 알아보겠습니다.

이 함수는 원본 배열에서 서로 다른 두 숫자를 선택하여, 그 합이 두 번째 인자로 전달된 숫자에 가장 가까운 쌍을 배열 형태로 반환해야 합니다.

문제 예시

배열 [1, 2, 3, 4, 5, 6, 7]과 목표 숫자 14가 주어졌을 때, 두 수의 합이 14에 가장 가까운(정확히 14가 되는) 쌍은 6과 7입니다. 따라서 함수는 [6, 7]을 반환해야 합니다.

구현 코드

const arr = [1, 2, 3, 4, 5, 6, 7];
const num = 14;
const closestPair = (arr, sum) => {
    let first = 0, second = 0;
    for(let i in arr) {
        for(let j in arr) {
            if(i != j) {
                let tmp = arr[i] + arr[j];
                if(tmp <= sum && tmp > first + second) {
                    first = arr[i];
                    second = arr[j];
                }
            }
        }
    }
    return [first, second];
};
console.log(closestPair(arr, num));

코드 동작 원리

위 코드는 다음과 같은 단계로 동작합니다.

• 결과로 반환할 두 숫자 first와 second를 0으로 초기화합니다.
• 중첩 반복문을 통해 배열 내 모든 숫자 쌍의 조합을 확인합니다.
• 인덱스가 서로 다른 경우(같은 요소를 두 번 선택하지 않도록), 두 숫자의 합 tmp를 계산합니다.
• tmp가 목표 합계보다 작거나 같고, 지금까지 찾은 최대 합(first + second)보다 크다면 first와 second를 갱신합니다.
• 모든 조합을 확인한 후 최종 결과 [first, second]를 반환합니다.

실행 결과

[6, 7]

참고 사항

이 알고리즘은 중첩 반복문을 사용하므로 시간 복잡도는 O(n²)입니다. 또한 목표 값보다 작거나 같은 합을 가진 쌍만 고려하기 때문에, 배열의 모든 쌍의 합이 목표 값보다 클 경우 [0, 0]이 반환됩니다. 성능이 중요한 환경이라면 배열을 먼저 정렬한 뒤 투 포인터(two pointer) 기법을 적용하여 O(n log n) 수준으로 최적화할 수 있습니다.