백준 온라인 저지, 이진탐색 / 9024번: 두수의합 (파이썬 / 백준 골드문제)

문제

여러 개의 서로 다른 정수 S = {a₁, a₂, …, a_n} 와 또 다른 정수 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} 등의 다섯 종류가 있다.

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

입력

프로그램은 표준입력으로 입력을 받는다. 프로그램 입력은 t 개의 테스트 케이스로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t 가 주어진다. 두 번째 줄부터 두 줄에 한 개의 테스트 케이스에 해당하는 데이터가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 두 개의 정수 n 과 K (2 ≤ n ≤ 1,000,000, -10⁸ ≤ K ≤ 10⁸ )가 한 개의 공백을 사이에 두고 입력된다. 두 번째 줄에는 n 개의 정수가 하나의 공백을 사이에 두고 주어지며, 각 정수의 최댓값은 10⁸ 이고, 최솟값은 -10⁸ 이다. 잘못된 데이터가 입력되는 경우는 없다.

출력

출력은 표준출력(standard output)을 사용한다. 입력되는 테스트 케이스의 순서대로 다음 줄에 이어서 각 테스트 케이스의 결과를 출력한다. 각 테스트 케이스의 출력되는 첫 줄에 입력으로 주어진 n 개의 정수들 중에서 서로 다른 두 정수의 합이 주어진 또 다른 정수 K 에 가장 가까운 두 정수의 조합의 수를 출력한다.

제한

예제 입력 1

4
10 8
-7 9 2 -4 12 1 5 -3 -2 0
10 4
-7 9 2 -4 12 1 5 -3 -2 0
4 20
1 7 3 5
5 10
3 9 7 1 5

예제 출력 1

1
5
1
2

힌트

접근 방법

- 이진탐색을 통해 문제를 해결한다.

코드

# https://www.acmicpc.net/problem/9024
# 접근 방법
# 이진탐색을 통해 문제를 해결한다.
import sys
input = sys.stdin.readline
tc = int(input())
for _ in range(tc):
    n, k = map(int, input().split())
    array = list(map(int, input().split()))
    array.sort()
    min_dist_sum = int(1e9)
    count = 0
    for i in range(n):
        v1 = array[i]
        start = i + 1
        end = n - 1
        while start <= end:
            mid = (start + end) // 2
            v2 = array[mid]
            if abs(k - (v1 + v2)) < min_dist_sum:
                count = 1
                min_dist_sum = abs(k - (v1+v2))

            elif abs(k-(v1+v2)) == min_dist_sum:
                count += 1
        
            if k > v1+v2:
                start = mid + 1
            elif k < v1+v2:
                end = mid - 1
            else:
                break
    print(count)