백준 9024 : 두 수의 합 (Python)

본문링크

🔑 『나의 코드』

import sys
input=sys.stdin.readline

T=int(input())


for i in range(T):
    N,K = map(int,input().split())
    L=sorted(list(map(int,input().split())))
    start=0 ; end=N-1 ; count=0 ; answer=abs(K- (L[start]+L[end]))
    # K 의 가장 가까운 수를 어떻게 찾을것인가? 일단 두 수의 합의 변수 answer를 start와 end의 합으로 한다.
    # 이후 count보다 K에 가까운수가 존재하면 count를 0으로 초기화하고 그 가까운수를 변수에 다시 저장한다.
    while start<end:
        if abs(K- (L[start]+L[end]) )<answer:
            count=1
            answer=abs(K- (L[start]+L[end]) )
            if K-(L[start]+L[end])>0:
                start+=1
            else:
                end-=1
        elif abs(K-(L[start]+L[end]))==answer:
            count+=1
            if K-(L[start]+L[end])>0:
                start+=1
            else:
                end-=1
        elif abs(K- (L[start]+L[end]))>answer:
            if K-(L[start]+L[end])>0:
                start+=1
            else:
                end-=1

    print(count)

🔑 『다른사람의 코드』

import sys
input=sys.stdin.readline

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

    mini=200000000
    for j in range(n):
        l=j+1
        r= n-1
        while(l<=r):
            mid=(l+r)//2
            s=num[j]+num[mid]
            if(s>k):
                r=mid-1
            else:
                l=mid+1
            if(abs(k-s)<mini):
                cnt=1
                mini=abs(k-s)
            elif(abs(k-s)==mini):
                cnt+=1
    print(cnt)

📌 K에 가장 가까운 두수의 합을 어떻게 구할것인가?

이 문제는 이분탐색&투 포인터 문제이다. 나는 '두 수의 합' 이라는 문장때문에 투포인터를 사용하였으나 이분탐색으로도 가능합니다. 투 포인터 코드에 대해 설명만 하겠습니다.

K의 가장 가까운 두 수의 합을 찾기 위해서는 K-두 수 의 합의 최소값을 매번 확인해서
더 가까운 새로운 최소값이 생기면 또다시 그 값을 기준으로 K-두 수 의 합의 최소값을 찾습니다.
그리고 최소값이 같지만 원소가 다를경우 경우의 수를 추가합니다.

먼저 리스트 L을 오름차순으로 정렬해준후 , start=0 end=N-1로 잡습니다.
count 변수는 중복되는 경우의 수를 담고 answer 변수는 그때의 K-두 수의 합의 최솟값을 담습니다.

만약 abs(K-(L[start]+L[end])) 값이 최솟값 (answer) 보다 작다면
새로운 경우가 나타났으므로 count=1 , 그리고 answer 변수를 다시 정의해줍니다.

반대로 abs(K-(L[start]+L[end])) 값이 최솟값 (answer) 보다 크다면 start 나 end 값을 변동시킵니다.

그리고 abs(K-(L[start]+L[end])) 값이 최솟값 (answer) 과 같으면 count 를 증가 시킵니다.
경우의 수가 늘어났기 때문입니다.

또한 매 조건마다 K-(L[start]+L[end]) 값이 0 보다 크면 0 에 가깝게 만들기 위해서
L[start]+L[end] 값을 증가 시켜야 하기 때문에 start+=1 을 해줍니다.

반대로 K-(L[start]+L[end]) 값이 0 보다 작으면 0 에 가깝게 만들기 위해서
L[start]+L[end] 값을 감소시켜야 하기 때문에 end-=1 을 해줍니다.

이후 마지막으로 count 를 출력하면 됩니다.

✅ 코드에서 중요한 부분

• start=0 ; end=N-1로 잡는다.

• while 문에서 start<end로 잡는다. 투 포인터이기 때문에 start와 end는 같을 수 없다.

• count=0; answer=abs(K-(L[start]+L[end])) 로 시작한다.

• K의 가장 가까운수를 찾을때마다 매번 K- 두 수의 합이 0보다 크거나 같은지 확인후 포인터를 이동한다.