[BaekJoon] 백준 2467번 : 용액

2467번 : 용액

가능한 모든 짝을 통해 답을 구해도 된다.

하지만 최대 100,000 개의 데이터가 주어지기 때문에 시간초과가 발생 할 것이다.

때문에 포인터 두 개를 사용해 움직여가며 답을 구하면 된다.

예를 들어 -120 -30 -7 -4 -2 6 10 18 20 이 있다고 하자.

start 는 0, end 는 N - 1 로 초기화 한 뒤 [start + 1] + [end] 와 [start] + [end - 1] 의 값을 구한다.

두 값중 더 0 에 가까운 점을 찾아 다시 start, end 에 대입한다.

이 과정을 반복하면 답을 구할 수 있다.

---

import sys


def solution():
    start, end = 0, N - 1
    answer = [water[start] + water[end], start, end]

    while start != end:
        left = [water[start] + water[end - 1], start, end - 1]
        right = [water[start + 1] + water[end], start + 1, end]

        if abs(left[0]) > abs(right[0]):
            tmp_answer = right
        else:
            tmp_answer = left

        if tmp_answer[1] != tmp_answer[2] and abs(answer[0]) > abs(tmp_answer[0]):
            answer = tmp_answer

        start, end = tmp_answer[1], tmp_answer[2]

    print(water[answer[1]], water[answer[2]])


if __name__ == "__main__":
    N = int(input())
    water = list(map(int, sys.stdin.readline().rsplit()))

    solution()