[python] BOJ 2470 두 용액

[intro]

문제의 핵심은 어떤 것을 이분탐색으로 풀 것인가?(사실 투포인터가 더 쉽고 빨리 끝나지만 이분탐색으로 풀어보았다.)

정렬된 용액들 중 가장 작은 값부터 순서대로 후보로 두고 나를 제외한 용액들 중에서 나와 합하여 최대한 0에 가까운 숫자를 만들 수 있는 짝을 찾는 과정

[코드 설명]

left 가 index + 1 인 이유 : nums 배열에서 index는 이번 순서에 선택된 한쪽 짝(고정) 나를 제외한 용액들 중 나의 짝을 찾기 위한 첫 지점은 내 다음번 순서가 되어야 한다. left를 index로 설정할 경우 나 자신도 짝 후보에 포함되기 때문에 주의하여야 함

ex>nums = [-99, -2, -1, 4, 98]

첫번째로 for 문이 돌 때

index = 0

left = index + 1 ⇒ 1

right = n - 1 ⇒ 4

candidate = -99

이분탐색하려고 하는 범위 -99의 다음번 index부터 끝까지

n = int(input())
nums = list(map(int, input().split()))
nums.sort()
mn = 2000000001
pair_1 = 0
pair_2 = 0

for index, candidate in enumerate(nums):
    left = index + 1
    right = n - 1

    while left <= right:
        mid = (left + right) // 2

        if candidate + nums[mid] == 0:
            mn = 0
            pair_1 = candidate
            pair_2 = nums[mid]
            break
        elif candidate + nums[mid] < 0:
            left = mid + 1
        else:
            right = mid - 1

        if mn > abs(candidate + nums[mid]):
            mn = abs(candidate + nums[mid])
            pair_1 = candidate
            pair_2 = nums[mid]

print(pair_1, pair_2)

처음에는 들어오는 숫자가 모두 양수이거나 모두 음수인 경우에는 이 방법이 비효율 적이라고 생각해서 접근하지 못했었다. 하지만 그런 최악을 고려해도 시간복잡도 안에 들어오고 모든 상황에 동일한 결과를 뽑을 수 있으면 알고리즘은 성립한다.

[찾은 오류]

if candidate + nums[mid] == 0: 일때 break를 통해 반복문을 탈출하기 때문에 mn = 0을 해줄 필요가 없다고 생각했다. (내가 원하는 pair들은 이미 찾았으므로)

하지만 mn = 0으로 최솟값이 변경되는 것을 막아주지 않으면 mn은 처음에 넣어준 들어올 수 없는 가장 큰수가 들어있어 그 다음턴에 어떤 페어가 들어와도 바뀌게 되어있다 이과정에서 내가 찾아놓은 최적의 값이 변경되는 일이 발생함 mn = 0을 넣고 싶지 않다면 0이되는 쌍을 찾았다면 프로그램을 종료시키는 방식을 택해도 된다.

21.11.14일 기준으로 mn = 0을 해주지 않고 제출하여도 정답 처리 되나 원래는 틀려야 함(곧 해당 케이스 반영 예정)

mn = 0 없을 때

mn = 0 있을 때