[백준/2467/파이썬] 용액

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

2467번: 용액

Problem

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

조건

• KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.
• 예를 들어, 주어진 용액들의 특성값이 [-99, -2, -1, 4, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액의 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.
• 첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

SOL

완전탐색 

N개중에서 2개를 뽑는 모든 경우를 봐주면 되지만, 그렇게되면, N^2 이 나오기 때문에, TL이 걸리게 된다.

그렇다면, O(N)으로 해결할 수 있는 방법이 있지 않은지 생각해본다.

 

Trouble Shooting - 선형적으로 탐색을 할 수 있을까? 

1. 양 끝에서 하나씩 선택해서 줄여온다.

- 정렬되어있기 때문에, 언뜻보면, 제일 작은값 + 제일 큰값의 느낌으로 하다보면, 가장 최선이 나오지 않을까 싶지만, 반례가 쉽게 발생한다. 예를들어, liquid = [-5,-3,0,1,2]가 있다하면, 여기서 최소는 -3 2 또는, 0 1 이 나와야한다.

하지만, 우리가 구현한 방법으로는 , [-5,2] , [-3,1] 을 뽑을겁니다. (서로 다른 두 용액이므로, 0,0은 불가능합니다).

즉, 양수+양수, 혹은 음수+음수가 최선이 될 수가 있습니다.

 

2. 양 끝에서 줄여오는걸 포기하면, TL이 발생하기 때문에, 추가 조건을 설정해주자.

liquid[Left] + liquid[Right] 를 해준 값을 _sum이라고 하자. 

조건에 맞게 두 개의 합이 "0"에 가까워 지려고 한다면, 두 숫자 사이의 gap을 줄이는 방식으로 구현을 해야한다.

따라서, 아래와 같이 생각할 수 있다. 

 

• _sum이 양수라면, 정렬되어있기 때문에, Right의 값을 왼쪽으로 옮겨서 , 더 작은 수를 더하게 해준다. 
  
  • 이해가 안된다면, 간단한 예시를 들어보면 된다. 
  • -5,-3,0,10,100 일때, -5 + 100 보다는 -5+10이 갭이 작기 때문이다. 
• -sum이 음수라면, 정렬되어 있기 대문에, left의 값을 오른쪽으로 옮겨서, 더 작은 수를 더하게 해준다. 

그리고, 답을 출력하기 위해서 , Left의 index와 right의 index를 저장하기 위한 answerL,answerR를 선언해줍니다. 

또, 두 개의 합보다 작으면, 값을 갱신시켜줘야하기 때문에, 갱신을 위한 max값 1개와 , 갱신시키는 과정을 넣어주면 끝!

# 용액 
import sys
input= sys.stdin.readline

N=int(input().rstrip())
liquid=list(map(int,input().split()))

left=0
right=N-1

answerL = 0
answerR = 0
_min=sys.maxsize

while left<right:
    _sum=liquid[left] + liquid[right]
    
    if abs(_sum) < _min:
        answerL=left
        answerR=right
        _min=abs(_sum)
    if _sum>0:
        right-=1
    elif _sum<0:
        left+=1
    else:
        break

print(liquid[answerL],liquid[answerR])