[투포인터] (백준_2470) 두 용액

📌 링크: https://www.acmicpc.net/problem/2470

 

📌 총평: 이문제 이진탐색으로 분류되어있는데 낚시다. 투포인터 문제다.

 

📌 헷갈렸던 부분:

✅ 이 문제는 양쪽 끝을 계속해서 비교하는 문제여서, 핵심은 양끝의 합 >0 이면 오른쪽-=1, 양끝의 합 <0이면 왼쪽+=1을 하는거였다.

나는 양끝의 합의 부호를 기준으로 보지 않고 바로 직접값이랑 합의 값을 비교해서 틀렸다. abs(arr[s] + arr[e-1]) < abs(arr[s] + arr[e]) 왜 절댓값 비교를 하면 안되냐하면, 값이 수렴하지 않고 진동할 수 있기 때문이다. 현재 수렴해야하는 값은 양끝의 합=0이 되는 것,

즉, 0으로 값이 수렴해야하므로 0이 기준이 되어야한다. 그래서 0보다 합이 크면 합을 줄이는 쪽인 왼쪽-=1 ~ 이런식으로 왼쪽,오른쪽 값을 조절하는 거다.

 

✅ 절댓값을 빠뜨려서 자꾸 틀렸다.

 

📌 풀이 1 (left, right 조정)

N = int(input())
arr = list(map(int,input().split()))
arr.sort()
left,right=0,N-1
min_sum=abs(arr[left]+arr[right])
final=[arr[left],arr[right]]
while left<right:
    current_sum = arr[left]+arr[right]

    if min_sum > abs(current_sum):
        min_sum=abs(current_sum)
        final=[arr[left],arr[right]]

    if current_sum == 0:
        break
    elif current_sum>0:
        right-=1
    else:
        left+=1

print(*final)

 

📌 풀이 2 (left for문 돌리면서 right 조정)

N = int(input())
arr = list(map(int,input().split()))
arr.sort()
e = N-1
min_sum = int(1e9)*2
left,right=0,0
for s in range(N):
    while s<e:
        current_sum = arr[s]+arr[e]
        if abs(current_sum)<min_sum:
            left,right=s,e
            min_sum=abs(current_sum)
        if current_sum>0:
            e-=1
        else:
            break

print(arr[left],arr[right])