Python으로 목표값보다 큰 숫자 쌍의 최소 합을 찾는 프로그램

nums라는 숫자 리스트와 target이라는 값이 주어졌을 때, target보다 커야 하는 숫자 쌍의 합 중에서 가장 작은 값을 찾아야 합니다.

예를 들어, 입력이 nums = [2, 4, 6, 10, 14]이고 target = 10이라면 출력은 12가 됩니다. 2와 10을 선택하면 합이 12로, target(10)보다 크면서 가능한 모든 쌍 중에서 가장 작은 값이기 때문입니다.

문제 해결 접근 방법

이 문제는 투 포인터(Two Pointer) 기법을 활용하면 효율적으로 해결할 수 있습니다. 리스트를 먼저 정렬한 뒤, 양쪽 끝에서 시작하는 두 개의 포인터를 이동시켜가며 조건을 만족하는 최소 합을 탐색합니다. 시간 복잡도는 정렬에 O(n log n), 탐색에 O(n)이 소요되어 매우 효율적입니다.

알고리즘 단계

• 리스트 nums를 오름차순으로 정렬합니다.
• n := nums의 크기
• answer := 10^10 (충분히 큰 초기값)
• i := 0, j := n - 1로 설정합니다.
• i < j인 동안 다음을 반복합니다:
  • 만약 nums[i] + nums[j] > target이면:
    • answer := answer과 (nums[i] + nums[j]) 중 더 작은 값
    • j := j - 1 (오른쪽 포인터를 왼쪽으로 이동해 더 작은 합을 탐색)
  • 그렇지 않으면:
    • i := i + 1 (왼쪽 포인터를 오른쪽으로 이동해 합을 증가시킴)
• answer를 반환합니다.

구현 예제

더 나은 이해를 위해 다음 파이썬 구현을 살펴보겠습니다.

class Solution:
   def solve(self, nums, target): nums.sort()
      n = len(nums)
      answer = 10 ** 10
      i, j = 0, n - 1
      while i < j:
         if nums[i] + nums[j] > target:
            answer = min(answer, nums[i] + nums[j])
            j -= 1
         else:
            i += 1
      return answer
ob = Solution()
nums = [2, 4, 6, 10, 14]
target = 10
print(ob.solve(nums, target))

입력

[2, 4, 6, 10, 14], 10

출력

12

이 알고리즘의 핵심은 정렬된 배열에서 두 수의 합이 target보다 클 경우, 더 작은 합을 얻기 위해 오른쪽 포인터를 줄여가고, target 이하일 경우에는 합을 키우기 위해 왼쪽 포인터를 늘려가는 방식입니다. 이를 통해 모든 쌍을 확인하지 않고도 선형 시간 안에 최적의 답을 찾을 수 있습니다.