[복기] 2470번: 두 용액

문제

백준 2470번: 두 용액

내 방식

투포인터 문제인줄 모르고 정수 범위가 -10e9 ~ 10e9라서 이분탐색으로 풀려고 했다. 리스트 정렬 후, 제일 왼쪽값을 제외한 리스트에서 왼쪽값과의 합이 0에 가까운 값을 이분탐색으로 찾으려 시도했다.

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
a.sort()

sum = 100000000
answer = [0, 1]
for i in range(n):
    start = i+1
    end = n-1
    while start <= end:
        mid = (start+end)//2
        result = abs(a[i] + a[mid])
        if result < sum:
            sum = result
            answer = [a[i], a[mid]]
            if sum == 0:
                break
        if mid-1 <= i or mid+1 > end:
            break
        if abs(a[i] + a[mid-1]) < abs(a[i] + a[mid+1]):
            end = mid-1
        else:
            start = mid+1
    if sum == 0:
        break

answer.sort()
print(answer[0], answer[1], end=' ')

예제에 대해선 정답이었지만, 시간초과가 뜨고 Pypy3로 제출해보니 그냥 틀렸었다. 방식 자체가 틀렸다 생각하고 솔루션을 봤다.

솔루션

2470 솔루션

투포인터 문제라고 한다. 절대값이 비슷한 음수와 양수를 합쳐야 0과 가까운 수가 나오기 때문에, 리스트 정렬 후 양쪽 끝에서부터 비교해나가면 된다고 한다. 정말 간단하다.. 아침이라 뇌가 덜 깼나..

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split(' ')))
arr.sort()

left = 0
right = n-1

answer = abs(arr[left] + arr[right])
final = [arr[left], arr[right]]

while left < right:
    left_val = arr[left]
    right_val = arr[right]

    sum = left_val + right_val
    if abs(sum) < answer:
        answer = abs(sum)
        final = [left_val, right_val]
        if answer == 0:
          break
    if sum < 0:
        left += 1
    else:
        right -= 1

print(final[0], final[1])