[백준 2470번] 두 용액

문제 링크 >> https://www.acmicpc.net/problem/2470

 

 

📋 문제

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다.

각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다.  

산성 용액의 특성 값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성 값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

 

같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성 값의 합으로 정의한다.

이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 

 

예를 들어, 주어진 용액들의 특성값이특성 값이 [-2, 4, -99, -1, 98]인 경우에는 특성 값이 -99인 용액과 특성 값이 98인 용액을 혼합하면 특성 값이 -1인 용액을 만들 수 있고, 이 용액이 특성 값이 0에 가장 가까운 용액이다.

참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

 

산성 용액과 알칼리성 용액의 특성 값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성 값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

 

 

👉 입력

첫째 줄에는 전체 용액의 수 N이 입력된다.

N은 2 이상 100,000 이하이다.

둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다.

이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다.

N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

 

 

👈출력

첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성 값을 출력한다.

출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다.

특성 값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그중 아무것이나 하나를 출력한다.

 

 

📝 풀이

❌ 첫 번째 풀이

import sys
input = sys.stdin.readline

n = int(input())
arr = sorted(list(map(int, input().split())))

if arr[0] < 0 and arr[-1] < 0:
  # 용액이 모두 알칼리성일 경우
  print(arr[-1], arr[-2])
elif arr[0] > 0 and arr[-1] > 0:
  # 용액이 모두 산성일 경우
  print(arr[0], arr[1])
else:
  start, end = 0, n-1
  minNum = 1000000001
  result = [(0, 0)]
  
  while start < end:
    num = arr[start] + arr[end]
    
    if num < minNum:
      minNum = num
      result.pop()
      result.append((arr[start], arr[end]))
    
    start += 1
    end -= 1
  print(*result[0], sep=' ')

 

용액이 모두 산성일 경우, 용액이 모두 알칼리성일 경우, 산성과 알칼리성이 섞여있을 경우로 케이스를 나누었다.

먼저 arr에 용액의 특성값을 담고 이를 정렬한다.

arr 인덱싱에 사용할 포인터인 start와 end에 각각 0, n-1의 값을 담는다.

그리고 while문 안에서 arr[start] + arr[end]의 값을 담은 num을 비교해가며 최솟값을 찾는다.

num이 최소값일 경우 result에 담고 start와 end의 값을 바꾸며 범위를 좁혀나간다.

 

이 풀이는 당연하게도... 틀렸다.

일단 합이 음수가 되는 경우 최솟값을 잘못 찾고 있기 때문이다.

예를 들어 입력이 [-99, -98, -3, -2, 98]과 같은 경우 정답은 -99와 98이지만 아래 사진처럼 계산해 -98과 -2가 출력된다.

 

 

따라서 비교할 때는 절댓값을 사용해야 하고 이 값에 따라 포인터를 움직이는 것도 다르게 설정해야 한다.

 

✔️ 두 번째 풀이

import sys
input = sys.stdin.readline

n = int(input())
arr = sorted(list(map(int, input().split())))

start, end = 0, n-1
minNum = 9223372036854775807
result = []
  
while start < end:
  num = arr[start] + arr[end]
    
  if abs(num) < minNum:
    minNum = abs(num)
    result = [arr[start], arr[end]]
    
  if num < 0:
    start += 1
  else:
    end -= 1
      
print(*result, sep=' ')

 

두 번째 풀이에서는 경우를 나누지 않고 바로 계산했다.

이 과정에서 최소값을 저장할 변수인 minNum의 값을 최대 정수인 9223372036854775807로 설정했다.

Python3에서는 사라진 문법이지만 기존 Python2의 sys.maxint의 값이 9223372036854775807과 같다고 한다.

 

arr에 정렬된 특성값들을 담고 arr 인덱싱을 할 start와 end를 0, n-1로 선언하는 것은 첫 번째 풀이와 동일하다.

while문을 돌며 num에 arr[start] + arr[end]의 값을 담는다.

그리고 num의 절댓값과 minNum을 비교한다.

만약 최소값이 갱신된다면 minNum에는 num의 절댓값을 넣어주고 result에 arr[start]와 arr[end]의 값을 저장해둔다.

 

그리고 num의 값이 0보다 큰지 작은지 비교한다.

만약 num이 0보다 작다면(음수라면) start를 움직이고 num이 0보다 크다면 end를 움직인다.

 

while문이 끝나면 result의 값을 출력한다.

 

 

 

참고로 백준 2467번 용액 문제도 이 문제와 동일한 것 같은데 왜 나누어져 있는지 모르겠다.

아무튼 위 코드로 2467번 용액 문제와 2470번 두 용액 문제 모두 통과할 수 있었다.

 

 

🔍 참조

python 최대 정수 https://www.delftstack.com/ko/howto/python/python-max-int/