[Solved] BOJ: 2467 | 용액

문제

합이 0에 가장 가까운 두 용액 조합 구하기

입력과 출력

입력

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 서로 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

출력

첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

---

문제 해결 요약

1. 리스트의 양 끝을 투포인터로 지정
2. 두 용액의 합을 계산해 0에 가까워지도록 양 끝의 포인터를 갱신시킴

코드 설명

import 및 입력받기

-

import sys
input = sys.stdin.readline

n = int(input())
m = list(map(int, input().split()))
m.sort()

• 용액 개수 n과 용액 리스트 m을 입력받음
• 용액 리스트를 오름차순 정렬

두 용액 조합 구하기

0에 가장 가까운 두 용액 조합을 구한다

-

i = 0
j = len(m)-1
best = (m[i], m[j])
while i < j:
    tmp = (m[i], m[j])
    if abs(sum(tmp)) <= abs(sum(best)): # 0이랑 차가 가장 작은지
        best = tmp
    if sum(tmp) == 0:
        break
    elif sum(tmp) > 0:
        j -= 1
    else:
        i += 1

• i, j: 리스트의 양 끝으로 투포인터를 초기설정
• best 0에 가장 가까운 조합을 저장할 변수 선언
• tmp와 0 사이의 거리가 best와 0 사이의 거리보다 작거나 같다면 best의 값을 tmp로 갱신
• tmp가 0이면 바로 while문 탈출
• tmp가 0보다 크다면 tmp를 더 작게 해줘야하므로 j를 한 칸 왼쪽으로 이동
• tmp가 0보다 작다면 tmp를 더 크게 해줘야하므로 i를 한 칸 오른쪽으로 이동

---

전체 코드

import sys
input = sys.stdin.readline

n = int(input())
m = list(map(int, input().split()))
m.sort()

i = 0
j = len(m)-1
best = (m[i], m[j])
while i < j:
    tmp = (m[i], m[j])
    if abs(sum(tmp)) <= abs(sum(best)): # 0이랑 차가 가장 작은지
        best = tmp
    if sum(tmp) == 0:
        break
    elif sum(tmp) > 0:
        j -= 1
    else:
        i += 1

print(best[0], best[1])