백준 2467 : 용액 (Python)

본문 링크

import sys
input=sys.stdin.readline


N=int(input())

L=sorted(list(map(int,input().split())))
start=0
end=N-1

count=abs(L[start]+L[end])
answer=[L[start],L[end]]

while start<end:

    if L[start]+L[end]<0:
        if abs(L[start]+L[end])<count:
            count=abs(L[start]+L[end])
            answer=[L[start],L[end]]
        start+=1
        
    elif L[start]+L[end]>0:
        if abs(L[start]+L[end])<count:
            count=abs(L[start]+L[end])
            answer=[L[start],L[end]]
        end-=1
        
    elif L[start]+L[end]==0:
        print(L[start], L[end])
        exit(0)

print(*answer)

📌 특성값이 0에 가장 가까운 용액을 만들어내는 경우를 어떻게 찾을것인가?

먼저 N의 범위는 (2<=N<=100000) 이고 완전탐색을 통해 O(N^2)으로 풀경우 시간초과가 발생할 수 있다.
따라서 투 포인터를 통해 문제를 접근해본다.

❓ 어떻게 투 포인터를 적용할 것인가?

먼저 리스트 L을 정렬시킨다.
start는 리스트의 시작점 , end는 리스트의 마지막점으로 잡는다.

만약 L[start]+L[end]의 합이 0보다 작다면 start값을 증가시킨다. 왜냐하면 start값을 증가시킬때 두 값의 합이 증가하고 0에 더 가까워질수 있기 때문이다.

count 변수는 두 수의 합의 절대값을 담고 , answer은 그때의 L[start]값과 L[end] 값을 담는다.

만약 abs(L[start]+L[end]) 값이 count 보다 작을때 , 0에 더 가깝다는 의미이므로
그 값을 count와 answer에 답아준다.

이 문제는 스페셜 저지이기 때문에 가장 0에 가까운 아무 리스트 값만 출력하면 된다.

✅ 코드에서 중요한 부분

• start=0 ; end=N-1로 잡아준다
• count의 처음 값은 abs(L[start]+L[end])로 잡아준다
• while문에서 start<end로 잡아준다. start와 end는 투 포인터이기 때문에 같을 수 없다.
• 만약 L[start]+L[end]==0이면 바로 break 한다.
• 두 리스트의 값이 count보다 작거나 클때 , 그 값을 저장하고 마지막에 start,end값을 증가시키거나 감소시킨다.