성능 요약
메모리: 127820 KB, 시간: 176 ms
분류
정렬, 이분 탐색, 두 포인터
문제 설명
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에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.
아이디어, 문제풀이
- 두 용액의 합이 0 에 가장 가까운 값을 찾는 문제
- target값을 따로 설정하지 않고, 0으로 잡으면 됨
- 합을 구하는게 아니고, 그 합에 가장 가까운 값을 이루는 두 원소를 출력해야함
TROUBLE SHOOTING
-
일단 이문제를 구현하고, 알고리즘을 작성하는데에는 많은 시간이 걸리지 않았다. 앞선 문제들을 풀어보기도 했고, 머릿속에서도 빠르게 구현이 됐다. 그런데 틀렸다.
#https://www.acmicpc.net/problem/2470 #두 용액 #2470 import sys input = sys.stdin.readline n = int(input()) n_list = list(map(int, input().split())) # print(n_list) n_list.sort() # print(n_list) start = 0 #end = n end = n - 1 min_target = float('inf') while start <= end: mid = (start + end) // 2 for i in range(n): chai = abs(n_list[mid] + n_list[i]) if min_target > chai: min_target = chai a = n_list[mid] b = n_list[i] # for i in # if min_target >= 0: # if min_target > 0: # start = mid + 1 # elif min_target < 0: # end = mid - 1 if min_target > 0: start = mid + 1 elif min_target < 0: end = mid - 1 print(a, b) # print(result) -
예제에 나와있는 입력값들은 잘 나왔다. 문제는 백준 통과가 전혀 안된다는 것이였다. 여러 조건들을 비교해가면서 수정도 해보고, 문제를 다시 읽어봐도, chat gpt에게 아무리 물어봐도, 더이상 수정해낼수가 없었다. chat gpt가 내가 만든 코드를 보며 투포인트라는 말을 했는데, 결국 그 투포인트가 이 문제의 해결방법 이였다.
-
투포인트 이분탐색에 관한 내용은 이분탐색 정리본에 추가해서 올릴 예정이지만, 이문제를 통해 간단하게 설명하면, 이문제를 이분탐색으로 풀게되는 순간, 완전탐색과 같아진다. 실제로 내 머릿속 알고리즘도, mid들을 모든 i와 비교해서 빼며 그 최소값을 계속 갱신해주는 방식 이였는데, 이는 시간복잡도로 표현하면 O(n^2) 이 된다.
-
투포인트 이분탐색은, 값이 두개일 경우, 그 값들을 비교하며 한칸씩 줄여 나간다. 실제로 아래 코드를 참조하면 start =+ 1, end -= 1 로 한칸씩 줄여나가게 되는데, 이렇게 되면 모든 용액들의 조합을 계산하고 조합해 볼 필요가 없어진다.
- chat gpt - 투포인트 방식은 두 개의 포인터를 이용하여 범위를 좁혀나가면서 필요한 부분만 비교하는 방식입니다.
-
원리에 대해서 공부하고 적용하니, 문제 자체는 쉽게 풀렸다. 이해도 빨리됐고… 근데 이 전에 풀었던 공유기 문제처럼, 다음번에 만난다면 이 문제에서의 용액처럼 두가지 이동점을 찾아내는게 힘들것 같다는 생각이 들었다. 연습이 답일까?
코드
import sys
input = sys.stdin.readline
n = int(input())
n_list = list(map(int, input().split()))
n_list.sort()
min_target = float('inf')
a, b = 0, 0
start = 0
end = n - 1
while start < end:
s = n_list[start] + n_list[end]
if abs(s) < min_target:
min_target = abs(s)
a, b = n_list[start], n_list[end]
if s > 0:
end -= 1
else:
start += 1
print(a, b)
# 위 코드는 투포인터 방식으로 작성된 코드입니다.
# start와 end 변수를 각각 첫 번째 용액과 마지막 용액의 인덱스로 초기화한 후,
# 반복문을 돌면서 두 용액의 합을 계산하고,
# 그 합의 절댓값이 현재까지의 최소 차이값보다 작으면
# 최소 차이값과 그 때의 두 용액 값을 업데이트합니다.
# 그리고 두 용액의 합이 0보다 크면 end 변수를 하나 줄이고,
# 0보다 작으면 start 변수를 하나 늘려나가면서 최소 차이값을 찾아냅니다.