BaekJoon 2470번 : 두 용액 (python)

BaekJoon 2470번 : 두 용액 (G5 31.043%)

해당 문제는 두 값의 합이 0에 가까울 경우의 조합을 구하는 문제이다.

• 시간복잡도를 O(N)의 투 포인터로 풀기 위해 입력받은 리스트를 정렬을 해준다.
• 투 포인터를 양 끝에서 시작하며 두 수의 합의 절댓값을 비교한다.
• 두 수의 합의 절댓값을 비교 변수와 비교해주고 비교 변수보다 작다는 것은 0에 가깝다는 것을 의미하고 이 때 비교 변수를 두 수의 합의 절댓값으로 갱신시켜주고 동시에 두 포인터이 위치를 저장을 한다.
  • 이 때 두 수의 합이 0보다 작을 경우 -를 뜻하는 알칼리성이 더 크다는 의미이기 때문에 알칼리성을 줄이기 위해 start를 한 칸 오른쪽으로 옮겨준다.
  • 만약 그렇지 않다면 두 수의 절댓값을 줄여주기 위해 end값을 왼쪽으로 한 칸 옮겨준다.
• 만약 두 수의 합의 절댓값이 비교 변수보다 크다면 위 비교 과정을 똑같이 반복하며 s나 e를 이동시켜준다.

import sys
input = sys.stdin.readline

n = int(input())

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

s = 0
e = n-1
temp = 1e10
x = 0
y = 0
#print(arr)
while s < e :
    if abs(arr[s] + arr[e]) < temp :
        temp = abs(arr[s] + arr[e])
        x, y = s, e
        if arr[s] + arr[e] < 0 :
            s += 1
        else :
            e -= 1
    elif abs(arr[s] + arr[e]) >= temp :
        if arr[s] + arr[e] < 0 :
            s += 1
        else :
            e -= 1
print(arr[x],arr[y])