[백준] #2470 두 용액 (Python)

1. 문제 설명

문제 링크

• 입력
  • 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다.
  • 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다.
• 출력
  • 첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

2. 코드

solution1.py

import sys
input = sys.stdin.readline

n = int(input())
ary = list(map(int, input().split()))
ary.sort()
left = 0 #맨 앞
right = n-1 #맨 끝

min_hab = 2000000001
answer = []

while left < right:
    L = ary[left]
    R = ary[right]

    hab = L + R
    # 두 용액의 합이 0과 가장 가까운 용액을 정답에 담아주기
    if abs(hab) < min_hab:
        min_hab = abs(hab)
        answer = [L, R]

    # 두 용액의합이 0보다 작다면 왼쪽의 값을 늘려 0에 가깝게
    if hab < 0:
        left += 1
    # 반대로, 두 용액의 합이 0보다 크다면 오른쪽의 값을 줄여서 0에 가깝게
    else:
        right -= 1

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

3. 회고

• left, right : 두 포인터는 양 끝에서 시작한다.
• min_hab : 0에 가까운 최소합
  • ary의 숫자가 -1,000,000,000 이상 1,000,000,000 이하 라는 조건이 있으므로 나올 수 있는 최대 차이인 2000000001로 초기화해준다.
• 투포인터 사용
  • 주어지는 ary의 최대길이가 100,000 이므로 투포인터를 사용해 푼다.
  • 두 용액의 합이 0보다 작으면 값을 조금 더 늘려서 0에 더 가까워지는지 확인해야하므로 왼쪽값을 늘려준다.
  • 두 용액의 합이 0보다 크면 값을 조금 더 줄여서 0에 더 가까워지는지 확인해야하므로 더 큰 값인 오른쪽 값을 줄여준다.
  • L과 R의 합의 절대값(0에서 얼마나 떨어졌는지)와 기존의 min_hab를 비교해가며 계속해서 min_hab을 더 작은 값으로 업데이트 해준다.
    • 그때마다 원소의 값을 answer에 업데이트 하다가 left < right가 아닌 순간에 종료하고 정답을 출력한다.

4. 참고

https://bladejun.tistory.com/97