[백준/2473/파이썬] 세 용액

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

2473번: 세 용액

Problem

• 같은 양의 세 가지 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 세 가지 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 
• 예를 들어, 주어진 용액들의 특성값이 [-2, 6, -97, -6, 98]인 경우에는 특성값이 -97와 -2인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 세 종류의 알칼리성 용액만으로나 혹은 세 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.
• 산성 용액과 알칼리성 용액이 주어졌을 때, 이 중 같은 양의 세 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 세 용액을 찾는 프로그램을 작성하시오.

조건

• 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

SOL

 

초등학생 -> 중학생 -> 고등학생까지 왔다..

 

완전탐색

 

완전탐색으로 구현하면, nC3이라서, N^3가 발생한다. 따라서, TL이 발생하게 된다.

 

투 포인터 응용 

하나를 정해놓고 + 투 포인터를 이용해서 풀어야한다. 여기서, 하나를 정했을 때, 탐색 범위를 정해줘야하는데, 

선택된 다음 원소부터 ~ N-1까지 탐색을 해주면 된다.

 

pypy3로 제출했을때, 아래의 코드는 통과하지만, python3에서는 통과를 하지 못한다.

# 세 용액

# 3가지 용액을 선택 
import sys
input= sys.stdin.readline

N= int(input().rstrip())
liquid=list(map(int,input().split()))
liquid.sort()
_min=sys.maxsize
ans=[0,0,0]
for i in range(N-2):
    left,right=i+1,N-1
    while left<right:
        _sum=liquid[i]+liquid[left]+liquid[right]
        if _min>abs(_sum):
            ans=[liquid[i],liquid[left],liquid[right]]
            _min=abs(_sum)
        if _sum<0:
            left+=1
        elif _sum>0:
            right-=1
        else:
            break

print(ans[0],ans[1],ans[2])

 

python의 내부적인 로직에서 차이가 발생하는 것이겠지만, 그래도 python으로 통과하기 위해서, 최대한 python 스럽게 코딩을 해봤다. 

iter(반복자)를 이용해서, liquids의 시작 , reveresed를 이용해서, liquids의 끝에서 부터 반복을 시작해준다.

이때, next를 이용해서 left,right를 추출해주고,  liquids의 길이만큼 , 반복을 시작한다.

 

import sys
input= sys.stdin.readline

def main():
    N= int(input().rstrip())
    liquids=[int(x) for x in input().split()]
    
    liquids.sort()
    _min=sys.maxsize
    
    for _ in range(N-2):
        liquid=liquids.pop()
        from_left,from_right=iter(liquids),reversed(liquids)
        left=next(from_left)
        right=next(from_right)
        for _ in range(len(liquids)-1):
            _sum=liquid+left+right
            if abs(_sum)<_min:
                _min=abs(_sum)
                answer=(left,right,liquid)
            if _sum<0:
                left=next(from_left)
            else:
                right=next(from_right)
        if _min==0:
            break
    print(*answer)

main()