문제
주어진 문제는 0이 아닌 정수값인 용액의 산도가 일련의 입력으로 들어온다.
알칼리성은 음수, 산성은 양수값을 가지며 가능한 0에 가까운 용액 조합을 찾는 것이 목표이다.
입력
용액의 수 N이 주어지고 이후에 -1,000,000,000 이상 1,000,000,000 이하의 0이 아닌 정수가 N개 입력된다.
출력
0에 가장 가까운 합을 가지는 용액의 산도 2개를 출력한다.
고민
이 문제의 입력은 오름차순, 내림차순의 순서를 가지지 않으며 출력은 용액이 들어온 순서에 관계없이 결정할 수 있다.
무식한 방법으로 접근한다면 모든 용액의 산도를 저장하고 0번 인덱스부터 N-1 인덱스까지 가능한 모든 조합을 검사하여 0에 가장 가까운 인덱스를 찾을 수 있을것이다. 하지만 이런 방식은 분명 시간제한에 걸리기 때문에 좀 더 효율적으로 검사할 방식을 구상해야한다.
해결
입력된 용액들의 순서가 출력에 영향을 주지 않기 때문에 이 값들을 오름차순으로 정렬해본다. 그럼 알칼리성, 산성에 따라 배열이 2개의 부분배열로 나뉘어지게 된다. 이러한 구조는 성질이 같은(부호가 같은) 두 개의 용액이 섞일 경우 0에서 더 멀어지게 되므로 검사할 필요가 없다는 것을 근거로 불필요한 비교를 생략하게 해준다.
용액이 0에 가깝다는 것은 절댓값으로 확인할 수 있다. 0에 가까울수록 절댓값이 작을 것이고 더 작은 절댓값을 가지는 인덱스를 결과로 저장한다.
알칼리성 용액, 산성용액을 하나씩 가리키기 위해 2개의 포인터를 사용해야한다.
산성 용액이나 알칼리성 용액의 산도값을 비교해보고 이전의 값보다 0에 가깝다면 결과로 출력할 값을 현재 산성 용액과 알칼리성 용액의 인덱스로 수정한다.
알칼리성 용액 포인터는 1씩 증가할 것이고, 산성 용액의 포인터는 1씩 감소한다. 두 포인터가 교차할 때 까지 반복검사하는데 중요한 점은 어떤 포인터를 이동시킬 것인가 이다.
나는 두 포인터 중에서 더 절댓값이 작은 산도를 가지는 포인터를 이동 시켰다. 두 포인터는 점차 가리키는 용액의 절댓값이 작아지는 방향으로 이동하게 된다. 두 포인터 중 절댓값이 작은 용액의 포인터를 움직이게 되면 되려 합의 절댓값이 커지게 된다.
import sys
# 1차 시도. 이진 탐색 이용 - 시간초과
# 입력으로 0이 들어오지 않는다.
def solve() :
n = int(sys.stdin.readline())
s = list(map(int, sys.stdin.readline().split()))
s.sort()
res = [0, n-1, s[0] + s[-1]]
alkali = 0
acid = n- 1
while alkali < acid :
if abs(res[2]) >= abs(s[acid] + s[alkali]) :
res[0], res[1], res[2] = alkali, acid, s[alkali] + s[acid]
if abs(s[alkali]) > abs(s[acid]) :
alkali +=1
else :
acid -= 1
print(s[res[0]], s[res[1]])
solve()