목표 합에 가장 가까운 두 수

자바스크립트 코딩테스트 문제로 two-pointers 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

algorithm medium two-pointers 함수명: solution 제한 시간: 300ms

오름차순으로 정렬된 정수 배열 nums와 목표값 target이 주어질 때, 합이 target에 가장 가까운 두 수를 [a, b] 형태로 반환하세요.

가장 가까운 쌍이 여러 개라면 첫 번째 수가 더 작은 쌍을 반환하고, 첫 번째 수도 같다면 두 번째 수가 더 작은 쌍을 반환합니다.

제한사항

• 2 <= nums.length <= 200,000
• nums는 오름차순으로 정렬된 정수 배열입니다.
• -1,000,000 <= nums[i] <= 1,000,000
• 같은 값이 여러 번 등장할 수 있습니다.
• -2,000,000 <= target <= 2,000,000
• 반환값은 조건을 만족하는 길이 2 배열 [a, b]입니다.
• 항상 서로 다른 두 인덱스를 사용해야 합니다.

예시

• 입력: nums = [1, 4, 6, 8, 10], target = 13 → 출력: [4, 10]
  • 가능한 합은 11, 14, 16... 등이 있고, 14와 13의 차이 1이 가장 작습니다.
• 입력: nums = [2, 5, 9, 12], target = 20 → 출력: [9, 12]
  • 9 + 12 = 21로 차이 1이 가장 작습니다.
• 입력: nums = [1, 2, 3, 7, 8], target = 10 → 출력: [2, 8]
  • [2, 8]과 [3, 7] 모두 정확히 10이지만, 동률이면 첫 번째 수가 더 작은 [2, 8]을 고릅니다.

힌트

• 배열이 이미 정렬되어 있다는 점이 핵심입니다.
• 맨 왼쪽과 맨 오른쪽을 먼저 잡고 현재 합을 확인해 보세요.
• 합이 target보다 작다면 더 큰 합이 필요하므로 왼쪽 포인터를 오른쪽으로 움직여야 합니다.
• 합이 target보다 크다면 더 작은 합이 필요하므로 오른쪽 포인터를 왼쪽으로 움직여야 합니다.

해설

이 문제는 모든 두 수 조합을 다 확인하면 O(n^2)이 됩니다. 배열 길이가 최대 200,000이므로 이렇게 풀면 너무 느립니다.

여기서 중요한 조건은 배열이 오름차순 정렬되어 있다는 점입니다. 이때 양끝에서 시작하는 투 포인터(two pointers) 전략을 사용할 수 있습니다.

풀이 아이디어

• left = 0, right = nums.length - 1로 시작합니다.
• 현재 합 sum = nums[left] + nums[right]를 계산합니다.
• sum이 target에 얼마나 가까운지 확인해서, 지금까지의 최선 답과 비교합니다.
• 그다음 포인터를 움직입니다.
  • sum < target 이면 합이 더 커져야 하므로 left++
  • sum > target 이면 합이 더 작아져야 하므로 right--
  • sum === target 이어도 바로 끝내지 말고, 동률 우선순위가 더 좋은 쌍이 있을 수 있으므로 비교 후 한 칸 더 진행할 수 있습니다. 이 문제에서는 첫 번째 수가 더 작은 쌍을 우선하므로 right--보다 left++가 항상 유리한 것은 아닙니다. 가장 단순한 방법은 현재 쌍을 기록한 뒤, 한쪽만 규칙적으로 움직이며 전체 탐색을 끝까지 유지하는 것입니다. 일반적으로는 sum <= target일 때 left++, sum > target일 때 right--로 구현하면 됩니다.

왜 이 방식이 맞을까?

정렬 배열에서:

• 현재 합이 너무 작다면, 더 큰 값을 써야 target에 가까워질 가능성이 있습니다.
• 현재 합이 너무 크다면, 더 작은 값을 써야 합니다.

즉 한 번의 비교만으로 어느 쪽 포인터를 움직여야 할지 결정할 수 있습니다. 그래서 모든 쌍을 보지 않아도 됩니다.

동률 처리

이번 문제는 절대 차이가 같은 경우에도 규칙이 있습니다.

1. 첫 번째 수가 더 작은 쌍 우선
2. 첫 번째 수도 같다면 두 번째 수가 더 작은 쌍 우선

따라서 후보를 갱신할 때는 단순히 차이만 비교하지 말고, 동률이면 [a, b]를 사전식으로 비교한다고 생각하면 됩니다.

시간 복잡도

• 각 포인터는 배열 끝에서 시작해 안쪽으로만 움직입니다.
• 따라서 전체 시간 복잡도는 O(n)입니다.
• 추가 공간은 몇 개의 변수만 쓰므로 O(1)입니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

입력값 []

아직 실행하지 않았습니다.

실행 결과

아직 실행하지 않았습니다.

예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.

댓글

문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.