[백준 14921번] 파이썬 - 용액 합성하기

백준 14921 - 용액 합성하기

시간 제한 1초, 메모리 제한 512MB

# 조건

• 홍익대 화학연구소는 다양한 용액을 보유하고 있다.
• 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데, 같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다.
• 당신은 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 하는데, 각 용액은 10ml시험관에 10ml씩 들어있고, 빈 20ml 시험관이 단 하나 있다.
• 게다가 용액을 계량할 수 없어서, 두 용액을 섞을 때는 10ml씩 섞어서 20ml로 만드는데, 단 한번밖에 할 수 없다.
• 그래서 미리 용액의 특성값들을 보고, 어떤 두 용액을 섞을 것인지 정해야 한다.
• 예를 들어, 연구소에 있는 용액들의 특성값이 [-101, -3, -1, 5, 93]이라고 하자.
  • 이 경우에 특성 값이 각각 -101, 93인 용액을 혼합하면 -8인 용액을 만들 수 있다.
  • 또한 특성값이 5인 용액과 93인 용액을 혼합하면 특성 값이 98인 용액을 만들 수 있다.
  • 모든 가능한 조합을 생각해 보면, 특성값이 2인 용액이 0에 가장 가까운 용액이다.
• 용액들의 특성값 A1, … ,AN이 오름차순으로 주어졌을 때, 이 중 두 개의 용액을 혼합하여 만들 수 있는 0에 가장 가까운 특성값 B를 출력하시오.

입력

N
A1 A2 … AN

출력

B

** 제한 사항**

• 2 ≤ N ≤ 100,000
• -100,000,000 ≤ Ai ≤ 100,000,000
• Ai-1 ≤ Ai

# 접근 방법

• 투 포인터를 이용하여 풀어준다.
• 0에 가까운 수를 만들기 위해선 양수 + 양수, 음수 + 음수보다는 음수 + 양수의 용액을 섞어야 한다.
• 따라서, 투 포인터를 양쪽 끝부터 시작하여 최솟값을 찾아나가면 된다.
• left = 0, right = N-1
• while문의 조건은 left < right
  • 내부 로직은 현재 값이 음수라면 left += 1, 양수라면 right -=1 을 해준다.
• 값을 비교할 때는 절댓값으로 해주어야 하지만, 저장해줄 때는 원본으로 해주어야 한다.

import sys  
si = sys.stdin.readline  

N = int(si())  
nums = [*map(int, si().split())]  

left = 0  
right = N-1  
result = float('inf')  
while left < right:  
    val = nums[left] + nums[right]  
    if abs(result) > abs(val):  
        result = val  
    if val < 0:  
        left += 1  
    else:  
        right -= 1  
print(result)