[Python] 9024번 두 수의 합

https://www.acmicpc.net/problem/9024

9024번: 두 수의 합

---

 

24/02/12

 

 

이전에 실패 했던 문제를 다시 풀어보았다. 전형적인 투 포인터 문제이지만, 포인터를 움직이는 방향에 유의해서 문제를 해결해야만 했었다.

---

 

문제 접근 방식:

 

 

특정한 값이 주어져 있고, 그 값에 가장 가까운 두 수의 합을 만들 수 있는 모든 조합을 찾는 것이 문제의 목표이다.

 

투 포인터 문제임을 보자마자 파악했지만, 포인터를 움직이는 방향에 유의해야만 했다.

 

나는 두 가지 경우로 분리해서 문제를 접근했다.

 

특정한 값보다 작으면서 그 값에 가장 가까운 두 수의 합을 만드는 경우와 특정한 값보다 크면서 그 값에 가장 가까운 두 수의 합을 만드는 경우로 분리했다.

 

두 경우 모두 오름차순으로 정렬된 배열을 입력으로 받는다.

 

이후 시작 포인터를 $0$, 끝 포인터를 $N-1$로 설정하여 두 포인터가 만날 때까지 움직여줬다.

 

특정한 값보다 작으면서 그 값에 가장 가까운 두 수의 합을 만드는 경우를 설명하면 다음과 같다.

 

먼저, 두 포인터가 가리키는 수의 합이 주어진 $K$보다 큰 경우, 특정한 값보다 작다는 조건과 맞지 않으므로 두 포인터가 가리키는 수의 합을 작도록 만들어주었다. 즉, 끝 포인터를 1만큼 감소시켜 주었다.

 

만약 그러지 않은 경우, 오차를 생각해 주는데 기존 오차보다 더 크게 나온다면 이는 두 수의 합이 $K$보다 훨씬 작은 것이므로, 두 수의 합을 크도록 만들어주었다. 즉, 시작 포인터를 1만큼 증가시켜 주었다.

 

오차가 기존 오차와 같다면 경우의 수를 하나 늘리고 시작 포인터를 1만큼 늘렸다.

 

오차가 기존 오차보다 작다면 갱신이 된 것이므로, 경우의 수를 1로 초기화시키고 시작 포인터를 1만큼 늘렸다.

 

이를 반복하면, 특정한 값보다 작으면서 그 값에 가장 가까운 두 수의 합을 만드는 모든 경우의 수를 구할 수 있다.

 

비슷하지만 시작 포인터와 끝 포인터를 증감하는 여부를 반대로만 바꿔주면 특정한 값보다 크면서 그 값에 가장 가까운 두 수의 합을 만드는 경우의 수를 구할 수 있다.

 

이 두 경우의 수를 모두 구한 뒤, 만약 두 경우의 수 모두 오차가 같다면 두 경우의 수를 더해주었고, 그렇지 않다면 오차가 더 작은 쪽으로 경우의 수를 정하도록 했다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 9024번 두 수의 합
# 두 포인터
import sys
input = sys.stdin.readline
MAX = 1_000_000_000

def nearest_1(N, K, sorted_arr): # 두 수의 합이 K보다 작을때
    start, end = 0, N-1
    min_error = MAX
    count = 0
    while start < end:
        val = sorted_arr[start] + sorted_arr[end]
        if val >= K:  # 두 수의 합이 K보다 크거나 같으면
            end -= 1 # 두 수의 합을 줄이려고 한다.
            continue
        error = K - val # 두 수의 합이 K보다 작은 상태에서 오차를 계산한다.
        if error == min_error: # 기존 오차와 같다면
            count += 1
            start += 1
        elif error < min_error: # 기존 오차보다 더 작다면
            count = 0
            count += 1
            start += 1  # val을 더 크도록 만든다.
            min_error = error
        else:  # 기존 오차보다 더 크다면 두 수의 합을 더 늘리려고 한다.
            start += 1
    return count, min_error

def nearest_2(N, K, sorted_arr): # 두 수의 합이 K보다 클때
    start, end = 0, N-1
    min_error = MAX
    count = 0
    while start < end:
        val = sorted_arr[start] + sorted_arr[end]
        if val < K:
            start += 1
            continue
        error = val - K
        if error == min_error:
            count += 1
            end -= 1
        elif error < min_error:
            count = 0
            count += 1
            end -= 1
            min_error = error
        else:
            end -= 1
    return count, min_error

def solve(N, K, sorted_arr):
    count1, error1 = nearest_1(N, K, sorted_arr)
    count2, error2 = nearest_2(N, K, sorted_arr)
    if error1 == error2:
        return count1 + count2
    elif error1 < error2:
        return count1
    else:
        return count2

def main():
    T = int(input())
    for _ in range(T):
        N, K = map(int, input().rstrip().split())
        sorted_arr = sorted(map(int, input().rstrip().split()))
        print(solve(N, K, sorted_arr))

main()