[백준 2470 / Python] 두 용액

두 용액

🔍 알고리즘 분류

• 투포인터

💡 문제 풀이

1. 배열 오름차순 정렬
2. 초기 포인터로 배열의 양 끝점 가리키고, 초기값(answer)을 두 지점의 합으로 설정
3. 두 값 더해주며 절댓값이 answer보다 작으면 갱신
4. 두 값의 합이 음수이면 start+1
5. 두 값의 합이 양수이면 end-1

📄 코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
arr.sort() # O(NlogN)

# 양 끝 지점 포인팅
start, end = 0, n - 1
ans_val = [arr[0], arr[1]]
answer = abs(arr[0] + arr[1])

# 투포인터 탐색: O(N)
while start < end:
    two_val = arr[start] + arr[end]
    if abs(two_val) < answer:
        answer = abs(arr[start] + arr[end])
        ans_val = [arr[start], arr[end]]
        if answer == 0:
            break
    # 합이 0보다 작으면 시작점 증가
    if two_val < 0:
        start += 1
    # 0보다 크면 끝점 감소
    else:
        end -= 1

# 오름차순 정렬 후 출력
ans_val.sort()
print(*ans_val)

• 시간복잡도: O(NlogN)