---

문제 링크

문제 링크

문제 요약

오름차순으로 구성된 배열에서 두 특성값의 합이 0에 최대한 가까운 조합을 찾아야 한다.
풀이법은 투 포인터와 이분 탐색이 있고, 각각 N과 Nlogn 의 시간 복잡도를 가진다.

투 포인터(N)

import sys

input = sys.stdin.readline

N = int(input())
M = list(map(int, input().split()))


def solution(N, M):
    start, end = 0, N - 1
    best = abs(M[start] + M[end])
    prev_start, prev_end = start, end
    while start < end:
        cur = M[start] + M[end]
        if best > abs(cur):
            best = abs(cur)
            prev_start, prev_end = start, end

        if cur < 0:
            start += 1
        elif cur == 0:
            break
        else:
            end -= 1

    print(M[prev_start], M[prev_end])


solution(N, M)

이분 탐색(NlogN)

import sys

input = sys.stdin.readline

N = int(input())
M = list(map(int, input().split()))


def solution(N, M):
    best = sys.maxsize
    best_start = 0
    best_end = N - 1
    for i in range(N - 1):
        val, end = bisect(i + 1, N - 1, i, best, M)
        if best > val:
            best = val
            best_start = i
            best_end = end

    print(M[best_start], M[best_end])


def bisect(left, right, cur, best, M):
    best_end = right
    while left <= right:
        mid = (left + right) // 2
        total = M[mid] + M[cur]

        if best > abs(total):
            best = abs(total)
            best_end = mid

        if total < 0:
            left = mid + 1
        else:
            right = mid - 1
    return best, best_end


solution(N, M)