문제

여러 개의 서로 다른 정수 S = {a1, a2, …, an} 와 또 다른 정수 K 가 주어졌을 때, S 에 속하는 서로 다른 두 개의 정수의 합이 K 에 가장 가까운 두 정수를 구하시오. 예를 들어, 10 개의 정수

S = { -7, 9, 2, -4, 12, 1, 5, -3, -2, 0}

가 주어졌을 때, K = 8 에 그 합이 가장 가까운 두 정수는 {12, -4} 이다. 또한 K = 4 에 그 합이 가장 가까운 두 정수는 {-7, 12}, {9, -4}, {5, -2}, {5, 0}, {1, 2} 등의 다섯 종류가 있다.

여러 개의 서로 다른 정수가 주어졌을 때, 주어진 정수들 중에서 서로 다른 두 정수의 합이 주어진 또 다른 정수에 가장 가까운 두 정수의 조합의 수를 계산하는 프로그램을 작성하시오.

import sys

input = lambda: sys.stdin.readline().strip()

t = int(input())
for _ in range(t):
  n, k = map(int, input().split())
  arr = list(map(int, input().split()))
  arr.sort()

  start, end = 0, n - 1
  sum, count = 2 * (10**8), 1
  while start < end:
    num = arr[start] + arr[end]
    result = abs(k - num)

    if result == sum:
      count += 1
    elif result < sum:
      sum = result
      count = 1

    start_num = abs(k - (arr[start + 1] + arr[end]))
    end_num = abs(k - (arr[start] + arr[end - 1]))
    if start_num <= end_num:
      start += 1
    else:
      end -= 1

  print(count)

풀이

• S 정렬 -> 두포인터 이용
• start(0), end(n - 1) 를 통해 두 수의 합과 k 의 차를 구한다.
• 현재의 조합보다 k의 차가 작다면 count를 1로 하고 그 차를 현재의 조합으로 한다.
• 현재의 조합과 k의 차가 같다면 count를 1 더한다.
• 새로운 조합을 찾는다.
• 새로운 조합을 찾는 경우 start를 증가시킨 경우의 차와 end를 감소시킨 경우의 차를 비교해 차가 더 작은 쪽으로 조합을 찾는다.

백준 9024 두 수의 합