[백준][파이썬] 2470번. 두 용액

문제

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

 

풀이

두 용액을 섞어서 특성값이 0에 가장 가까운 용액을 만들어내는 문제이다.

우선 입력받은 용액의 특성값들을 오름차순으로 정렬한 후, 투 포인터를 사용해 풀이했다.

• 산성 용액 또는 알칼리성 용액만으로 이루어진 입력이 들어오는 경우
  • 절댓값이 가장 작은 값 2개를 더할때 특성값이 0에 가장 가까운 용액이 만들어진다.
• 산성, 알칼리성 용액이 모두 포함된 입력이 들어오는 경우
  • 양쪽 끝의 용액들을 더하는 것으로 시작해서, 인덱스를 하나씩 옮겨가며 특성값의 합을 계속 비교한다.
  • 특성값의 합이 0보다 작다면, 더 큰 수를 더해야 한다는 뜻이므로 왼쪽 인덱스를 하나 증가시킨다.
  • 특성값의 합이 0보다 크다면, 더 작은 수를 더해야 한다는 뜻이므로 오른쪽 인덱스를 하나 감소시킨다.

N = int(input())
Ns = list(map(int, input().split()))
Ns.sort()  # 오름차순 정렬

# 모든 용액의 특성값이 음수이거나, 양수인 경우 -> 절댓값이 가장 작은 값 2개를 더해야 함
if Ns[-1] < 0 :  # 특성값이 모두 음수 (모두 알칼리성 용액)
  print(Ns[-2], Ns[-1])
elif Ns[0] > 0 :  # 특성값이 모두 양수 (모두 산성 용액)
  print(Ns[0], Ns[1])

# 특성값에 음수와 양수가 섞여있는 경우
else :
  sum = 1e9
  left, right = 0, N-1
  while (left < right) :
    temp = Ns[left] + Ns[right]
    if abs(sum) > abs(temp) :  # 현재 두 용액의 합이 기존의 합보다 0에 더 가까운 경우 -> 정답 후보 갱신
      sum = temp
      answer = [Ns[left], Ns[right]]
    if temp < 0 :  # 합이 0보다 작다 -> 합이 더 커져야 한다 -> 더 큰 수를 더해야 한다 -> 왼쪽 인덱스 증가
      left += 1
    elif temp > 0 :  # 합이 0보다 크다 -> 합이 더 작아져야 한다 -> 더 작은 수를 더해야 한다 -> 오른쪽 인덱스 감소
      right -= 1
    else :  # temp == 0 : 합이 0이므로 더 볼 필요 없음
      break
  print(*answer)