문제
KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.
같은 양의 세 가지 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 세 가지 용액을 혼합하여 특성값이 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개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.
출력
첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 세 용액의 특성값을 출력한다. 출력해야하는 세 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.
내 풀이
pypy3 정답
python3에서는 시간 초과가 뜬다...
import sys
input = sys.stdin.readline
n = int(input())
liquids = list(map(int, input().split()))
liquids.sort()
a, b, c = 0, 0, 0
minsum = float('inf')
for i in range(n-2):
left = i+1
right = n-1
while left < right:
sum1 = liquids[i]+liquids[left]+liquids[right]
if abs(sum1) < abs(minsum):
minsum = sum1
a, b, c = liquids[i], liquids[left], liquids[right]
if sum1 == 0:
print(a, b, c)
sys.exit(0)
elif sum1 > 0:
right -= 1
else: # sum1 < 0
left += 1
print(a, b, c)python3 정답
import sys
input = sys.stdin.readline
n = int(input())
liquids = sorted(list(map(int, input().split())))
def solution():
a, b, c = 0, 0, 0
minsum = float('inf')
for i in range(n-2):
left = i+1
right = n-1
while left < right:
sum1 = liquids[i]+liquids[left]+liquids[right]
if abs(sum1) < minsum:
minsum = abs(sum1)
a, b, c = liquids[i], liquids[left], liquids[right]
if sum1 == 0:
return a, b, c
elif sum1 > 0:
right -= 1
else: # sum1 < 0
left += 1
return a, b, c
print(*solution())시간 복잡도 →
.sort()하는데
for문으로0~n-2까지 순회하며 그 안에서 투 포인터 탐색공간 복잡도 →
liquids배열 사용
코멘트
백준 2467 용액 문제를 풀지 않았다면 그것부터 풀고 이 문제에 도전하자. 2467은 생각보다 단순한 문제지만, 이 문제는 용액이 3개가 되면서 포인터를 어떤 것을 선정해서 어떻게 움직어야할지 멘붕이 온다. 하지만 해결 방법은 의외로 단순한데, 그냥 순차적으로 0 ~ n - 2까지 for문을 돌면서 하나의 용액을 선택하고 그 용액의 바로 다음 용액을 left, 가장 오른쪽 용액을 right로 설정하면 된다. 이후는 2467 용액 문제랑 똑같이 투 포인터로 풀면 된다.
로직은 위 문단에서 설명한 것처럼 생각보다 간단히 짤 수 있는데 자잘한 요소들을 신경쓰지 않아서 시간 초과를 많이 받았고, 그래서 더 효율적으로 고치느라 애먹었다.
liquids.sort()보다는liquids = sorted(list(map(int, input().split())))처럼 입력받을 때 정렬하는 것이 보다 빠르다고 한다.처음에는
if abs(sum1) < abs(minsum): minsum = sum1처럼 했었는데, 이러면 매번abs()연산이 들어가서 탐색이 많이 진행될수록 시간이 더 오래 걸린다고 한다. 따라서if abs(sum1) < minsum: minsum = abs(sum1)과 같이 수정하는 것이 좋다.⭐️ 가장 중요한 포인트 : 종료 방식
pypy3 코드에서는sum1 == 0일 때sys.exit(0)로 종료하고 있는데, 이는 파이썬 인터프리터 전체를 종료시키는 방식이라, BOJ 채점 서버에 따라 느려질 수도 있다고 한다. 대신 탐색하는 과정을 함수로 만들어서sum1 == 0일 때return으로 함수를 종료하게 하면 보다 빠르고 안전하게 종료된다. 이렇게 수정한 코드는 python3 채점에서도 시간 초과 없이 잘 작동한다.
References
https://www.acmicpc.net/problem/2473