JavaScript에서 주어진 숫자보다 작은 두 요소의 최대 합 구하기

이번 문제에서는 첫 번째 인자로 숫자 배열 arr을, 두 번째 인자로 하나의 숫자 num을 받는 JavaScript 함수를 작성해야 합니다.

함수의 목표는 배열에서 두 개의 수를 골라 그 합이 num보다 작으면서 가능한 한 가장 큰 경우를 찾는 것입니다. 만약 합이 num보다 작은 두 수의 조합이 존재하지 않는다면 함수는 -1을 반환해야 합니다.

문제 예시

예를 들어 입력 배열과 숫자가 다음과 같다고 가정해 보겠습니다.

const arr = [34, 75, 33, 23, 1, 24, 54, 8];
const num = 60;

이때 기대되는 출력 결과는 다음과 같습니다.

const output = 58;

34 + 24 = 58이 60보다 작으면서 만들 수 있는 가장 큰 합이기 때문입니다.

해결 접근 방식

이 문제는 정렬과 투 포인터(Two Pointer) 기법을 활용하면 효율적으로 해결할 수 있습니다. 배열을 오름차순으로 정렬한 뒤, 양쪽 끝에서 출발하는 두 포인터를 사용합니다.

두 포인터가 가리키는 수의 합이 num보다 작다면, 현재 합을 최댓값 후보로 저장하고 왼쪽 포인터를 오른쪽으로 이동시켜 더 큰 합을 시도합니다.
합이 num 이상이라면, 오른쪽 포인터를 왼쪽으로 이동시켜 합을 줄입니다.
두 포인터가 교차하면 탐색을 종료하고 지금까지 저장된 최댓값을 반환합니다. 조건을 만족하는 조합이 없었다면 초기값인 -1이 그대로 반환됩니다.

이 방식의 시간 복잡도는 정렬에 O(n log n), 탐색에 O(n)으로 매우 효율적입니다.

구현 코드

위 접근 방식을 적용한 전체 코드는 다음과 같습니다.

const arr = [34, 75, 33, 23, 1, 24, 54, 8];
const num = 60;

const lessSum = (arr = [], num = 1) => {
   arr.sort((a, b) => a - b);
   let max = -1;
   let i = 0;
   let j = arr.length - 1;
   while(i < j){
      let sum = arr[i] + arr[j];
      if(sum < num){
         max = Math.max(max, sum);
         i++;
      }else{
         j--;
      };
   };
   return max;
};
console.log(lessSum(arr, num));

출력 결과

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