[ BOJ 2470 ] 두 용액(Python)

문제

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

0에 가깝게 만드는 두 수를 찾으면 된다.

문제 풀이

0. 배열 입력 받기

sol = sorted(list(map(int,input().rsplit())))

입력 받을 때 정렬이 되도록 해주었다.

1. 이분 탐색 범위 구하기

l, r = 0, n-1

배열의 인덱스를 넣어주었다.

2. 변수 선언

lowest = sys.maxsize
low_l, low_r = 0, 0

0에 가까운 값을 저장해줄 lowest 변수와
두 용액의 값을 저장해 줄 변수 low_l, low_r을 선언한다.

3. 범위 체크

if abs(sol[l] + sol[r]) < lowest:
    lowest = abs(sol[l] + sol[r])
    low_l, low_r = sol[l], sol[r]
else:
    if abs(sol[l]) < abs(sol[r]):
        r -= 1
    else:
        l += 1

가장 작은 값과 가장 큰 값부터 비교를 해준다.

이때 더한 값이 음수일지 양수일지 알 수 없기 때문에 abs를 통해 절댓값으로 만들어주었다.
(; 절댓값이 작을 수록 0에 가까운 숫자이다.)

lowest와 비교해서 더 작은 값을 변수에 할당해준다.

만약 절댓값(두 수를 더한 값)이 lowest보다 클 때,
절댓값(왼쪽에 위치한 수) 보다 절댓값(오른쪽에 위치한 수)이 클 경우 최대 범위를 한 칸 앞으로 이동해준다.

반대의 경우엔 최소 범위를 한 칸 뒤로 이동해준다.

input) -99, -98, -97, -96
output) -97, -96

input) 1, 2, 3, 4
output) 1, 2

코드

import sys
input = sys.stdin.readline

# 0에 가까운 두 용액 찾기
n = int(input())
sol = sorted(list(map(int,input().rsplit())))

l, r = 0, n-1
lowest = sys.maxsize
low_l, low_r = 0, 0

while l < r:
    if abs(sol[l] + sol[r]) < lowest:
        lowest = abs(sol[l] + sol[r])
        low_l, low_r = sol[l], sol[r]
    else:
        if abs(sol[l]) < abs(sol[r]):
            r -= 1
        else:
            l += 1

print(low_l, low_r)