두 용액

문제

풀이(이진 탐색)

아이디어는 다음과 같다.
만약 정렬된 배열 [-99 -2 -1 4 98]이 있을 때
-99가 0이 되려면 99가 되어야 한다.
즉 이진탐색을 사용하면 [-99 -2 -1 4 98 99]가 될 것이고 반환되는 인덱스는 5가 될 것이다.
즉 배열에서 99와 가장 가까운 것은 5 기준으로 +1, -1이 될 것이다.

import sys
for test_case in range(1):
    n = int(sys.stdin.readline())
    arr = list(map(int, sys.stdin.readline().split()))
    arr.sort()


    def binary_search(num):
        start = 0
        end = n - 1

        while start<=end:
            mid = (start + end) // 2

            if arr[mid] > num:
                end = mid - 1
            else:
                start = mid + 1
        return end

    min_total = float('inf')
    result = []
    for i in range(n):
        num = arr[i]
        idx = binary_search(num*-1)

        cases = [idx, idx + 1, idx - 1]
        min_num = float('inf')
        tmp = -1
        for case in cases:
            if 0 <= case < n:
                if min_num > abs(num + arr[case]):
                    min_num = abs(num + arr[case])
                    tmp = case
        if i == tmp:
            continue
        if min_total > min_num:
            min_total = min_num
            result = [num, arr[tmp]]

    result.sort()
    print(' '.join(map(str, result)))

여기서

if i == tmp:
   continue

이부분은 같은 인덱스를 제외하는 경우이다.

풀이(투 포인터)

0이라는 특정 값을 찾는 것이면 투 포인터도 고려해 볼 수 있다.
정렬된 배열 [-99 -2 -1 4 98]이 있을 때

ans = 무한, start = 0, end = 4 로 양 끝에 두고 시작해보자

[step1] start = 0 end = 4일 때
arr[start] => -99
arr[end] => 98
둘이 더하면 -1이 된다. ans는 abs(-1)과 비교하여 최소값인 1을 저장한다.
또한 -1이므로 start를 +1한다.

[step2] start = 1 end = 4일 때
arr[start] => -2
arr[end] => 98
둘이 더하면 96이 된다. ans = min(1, 96)이 된다.
또한 96이므로 end를 -1한다.

[step3] start = 1 end = 3일 때
arr[start] = -2
arr[end] => 4
둘이 더하면 2가 된다. ans = min(1, 2)가 된다.
또한 2이므로 end를 -1한다.

이런식으로 하면 최소값은 1이 나오게 된다.

import sys

for test_case in range(1):
    n = int(sys.stdin.readline())
    arr = list(map(int, sys.stdin.readline().split()))
    arr.sort()

    start = 0
    end = n - 1
    ans = float('inf')
    tmp = []
    while start < end:
        cur = arr[start] + arr[end]

        if ans > abs(cur):
            ans = abs(cur)
            tmp = [arr[start], arr[end]]

        if cur == 0:
            break

        if cur > 0:
            end -= 1
        else:
            start += 1

    tmp.sort()

    print(' '.join(map(str, tmp)))