백준_2470_두용액/Using(Python/파이썬)

Problem

https://www.acmicpc.net/problem/2470

2470번: 두 용액

 

About Problem

두 용액을 합하여 0에 가까운 수를 만드는 문제이다.

input이 2이상 100,000 이므로 완전탐색은 할 수 없다. 정렬을 통해서 조건을 통해서 양끝을 줄여가면 빅오 N으로 값을 찾을 수 있다. 이 방식이 바로 two pointer다. 이 문제와 같이 two pointer는 두 값을 비교해서 특정 조건을 찾을 때 자주 쓰인다. 

Code

from sys import stdin

# 입력받기
N = int(stdin.readline())
lst = list(map(int, stdin.readline().split()))
# 정렬하기
lst.sort()

# two pointer 시작점과 끝점
s, e = 0, N-1

# min_num 값을 가장 큰 값으로 대입함
min_num = int(4e9)

# 투포인터 방식(끝값이 시작값보다 클때만 계속 돌게하기)
while e > s:
    # 두 값을 합한 total 값을 min_num과 비교
    total = lst[s] + lst[e]
    # 만약 min_num보다 작으면 갱신
    if abs(total) < min_num:
        min_num = abs(total)
        answer = [lst[s], lst[e]]

    # total이 0보다 크거나 같을 경우에는 e 값을 1씩 빼주면서 비교하기
    if total >= 0:
        e -= 1
    
    # total이 0보다 작을 경우에는 s 값을 1씩 더해주면서 비교하기
    elif total < 0:
        s += 1
        
print(*answer)