[BOJ] 2470 두 용액 | Python

문제

백준 2470번 두 용액 | 골드5

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

2470번: 두 용액

 

• 알고리즘 분류: 정렬 | 이분 탐색 | 투 포인터

 

 

 

 

풀이 과정

파이썬 풀이

import sys
input = sys.stdin.readline

n = int(input())
lst = sorted(list(map(int, input().split())))
a, b = 0, 0
value = 2000000000

i = 0
j = len(lst) - 1
while j > i:
    tmp = lst[i] + lst[j]
    if abs(tmp) < value:
        value = abs(tmp)
        a, b = lst[i], lst[j]
        if tmp == 0:
            break

    if tmp < 0:
        i += 1
    elif tmp > 0:
        j -= 1

print(a, b)

• 리스트를 정렬한 뒤, 앞에서 시작하는 i와 뒤에서 시작하는 j를 사용해 투 포인터로 풀이
• i, j번째 값들을 합하여 절대값이 낮으면 value, a, b를 각각 합한 값의 절대값, i, j로 지정한다. 0이면 더 구할 필요가 없으므로 종료
• tmp가 0보다 작으면 더 큰 값끼리 더하기 위해 i를 1씩 늘리고, 반대의 경우 작은 값을 더하기 위해 j를 줄인다.