문제링크

세 용액

문제설명

용액의 특성을 나타내는 정수가 있다. 산성은 1~1,000,000,000 알칼리성은 -1,000,000,000~-1로 나타낸다. 주어진 용액들중 세 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 세 용액을 구하라

문제풀이

시도 1

import sys
from itertools import combinations

input = sys.stdin.readline
N = int(input())
solution = list(map(int, input().split()))
solution.sort()

three_sol = list(combinations(solution, 3))
min_val = float('inf')
answer = [solution[0], solution[1], solution[2]]

for sol in three_sol:
    total = sum(sol)
    if abs(min_val) > abs(total):
        min_val = total
        answer = [sol[0], sol[1], sol[2]]

for ans in answer:
    print(ans, end=" ")

일단 단순하게 combinations를 이용하여 용액들 중 세가지를 뽑고 더한 값을 비교했다.
메모리초과가 발생했다^_ㅠ,,

시도 2

진챠 모르겠어서 구글링,,
-> 정렬과 투포인터를 사용해서 풀어야 된다고 한다.
투포인터는 한번도 풀어본 적이 없는걸,, 공부해서 재도전 간다 ㅋ
정보참고님의 블로그를 참고해서 풀이했다.

import sys

input = sys.stdin.readline
N = int(input())
solution = list(map(int, input().split()))
answer = []
min_val = float('inf')

#세 용액중 하나를 기준으로 잡고 양끝의 투포인터 이동하면서 값 비교
for i in range(N-2):
    #이전 기준이랑 값이 같으면 굳이 한번 더 비교할 필요 없으므로
    if i>0 and solution[i] == solution[i-1]:
        continue
    start, end = i+1, N-1
    while start < end:
        total = solution[i] + solution[start] + solution[end]
        if abs(total) < abs(min_val):
            min_val = total
            answer = [solution[i], solution[start], solution[end]]
        #sum의 값이 작으면 start를 오른쪽으로 옮겨서 커지게
        if total < 0:
            start += 1
        #sum의 값이 크면 end를 왼쪽으로 옮겨서 작아지게
        elif total > 0:
            end -= 1
        else:
            answer = [solution[i], solution[start], solution[end]]
            break
for ans in answer:
    print(ans, end=" ")

1. 용액의 특정 값들을 정렬
2. 하나를 기준으로 잡고 양끝의 투포인터 이동하면서 합이 0과 가장 가까운 세 조합 찾기

쉽지 않았내,,,, 다시 풀어봐야겠다