백준 9024번 두 수의 합

문제

여러 개의 서로 다른 정수 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} 등의 다섯 종류가 있다.

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

입력

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

출력

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

 

2. 코드

import sys

input = sys.stdin.readline

for test_case in range(int(input())):
    n, k = map(int, input().split())
    nums = list(map(int, input().split()))

    nums.sort()

    s, e = 0, len(nums) - 1
    ans = 0
    mn = 1e9

    while s < e:
        hap = nums[s] + nums[e]

        if mn > abs(k - hap):
            mn = abs(k - hap)
            ans = 0

        if hap < k:
            if abs(k - hap) == mn:
                ans += 1
            s += 1
        elif hap > k:
            if abs(k - hap) == mn:
                ans += 1
            e -= 1
        else:
            ans += 1
            s += 1
    print(ans)

 

3. 문제 해결법

1. n의 범위를 보아 이중 반복문시 100% 시간초과 이다.

2. 시간 초과를 벗어나기 위해 투포인터를 활용 한다.

3. 우선 입력 받은 숫자들을 sort를 통해 정렬를 해준다.

4. start, end 을 0, len(nums) - 1 로 지정하고, 최솟값을 비교 해주기 위한 mn = 1e9으로 설정

5.while start < end 즉 start가 end를 넘어 가는 순간 계산 할 필요가 없어 짐을 이용한다.

6. hap = nums[start] + nums[end] 두고 mn 과 hap - k 의 절댓값을 지속적으로 비교 해준다.

7.만약 mn 보다 작은 친구가 생기면 그 친구를 mn으로 설정하고 정답 변수를 0으로 초기화

8.이제 hap 이 mn 보다 클때, 작을때, 같을때를 만들어 투포인터를 활용하면 된다.