파이썬으로 목표 값보다 작은 두 수의 최대 합을 찾는 프로그램

숫자 리스트 nums와 목표 값(target)이 주어졌을 때, 두 수의 합이 목표 값보다 작은(즉, target-1 이하인) 쌍 중에서 가장 큰 합을 구하는 문제입니다.

예를 들어, nums = [8, 3, 4, 9, 2]이고 target = 8이라면 출력 결과는 7이 됩니다. 8 미만의 두 수 조합 중 가장 큰 합은 4 + 3 = 7이기 때문입니다.

문제 해결 접근 방법

이 문제는 정렬과 투 포인터(Two Pointer) 기법을 활용하면 효율적으로 해결할 수 있습니다. 전체적인 흐름은 다음과 같습니다.

리스트 nums를 오름차순으로 정렬합니다.
p1 := 0 (리스트의 시작 인덱스)
p2 := 리스트 길이 - 1 (리스트의 마지막 인덱스)
m := -inf (최댓값 저장 변수 초기화)
p1 < p2인 동안 아래 과정을 반복합니다.
- 만약 nums[p1] + nums[p2] < target이라면
  - m := max(m, nums[p1] + nums[p2])로 최댓값을 갱신합니다.
  - p1 := p1 + 1 (왼쪽 포인터를 한 칸 앞으로 이동)
- 그렇지 않다면
  - p2 := p2 - 1 (오른쪽 포인터를 한 칸 뒤로 이동)
반복이 종료되면 m을 반환합니다.

두 포인터가 서로 좁혀지면서 모든 유망한 조합을 검사하게 되므로, 정렬에 O(n log n), 탐색에 O(n)의 시간 복잡도로 문제를 해결할 수 있습니다.

예시 코드

아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.

import math
def solve(nums, target):
   nums.sort()
   p1 = 0
   p2 = len(nums) - 1
   m = -math.inf
   while p1 < p2:
      if nums[p1] + nums[p2] < target:
         m = max(m, nums[p1] + nums[p2])
         p1 += 1
      else:
         p2 -= 1
   return m

nums = [8, 3, 4, 9, 2]
target = 8
print(solve(nums, target))

입력

[8, 3, 4, 9, 2], 8