[BOJ] 용액

---

코드

import sys
input = sys.stdin.readline

n = int(input())
nums = list(map(int, input().split()))

# 절댓값 크기를 기준으로 정렬
for i in range(len(nums)):
    nums[i] = (nums[i], abs(nums[i]))    # (원래 값, 절댓값)
nums.sort(key=lambda x: x[1])

# 정렬한 배열에서 인접한 두 수의 합이 0에 가장 가까운 것을 탐색
abs_sum = sys.maxsize
ans = []
for i in range(len(nums)-1):
    sum = nums[i][0] + nums[i+1][0]
    if abs(sum) < abs_sum:
        abs_sum = abs(sum)
        ans = [nums[i][0], nums[i+1][0]]
    
print(' '.join(map(str, sorted(ans))))

결과

풀이 방법

• 100000개 중에서 두 수를 임의로 골라서 풀 수는 없는 문제이다.
• 두 수의 합이 0에 가장 가까우려면 입력받은 수들이 각각의 절댓값 기준으로 정렬되어 있는 상태에서 탐색하는 것이 편할 것 같았다.
• 모든 수들이 절댓값 기준으로 정렬되어 있다면, 모두 양수이거나 모두 음수이더라도 답을 찾는 데 문제가 없다.
• 또한 인접한 수들끼리 절댓값 차이가 가장 작기 때문에 정렬한 배열에 부호가 다른 수가 하나라도 있다면 그와 인접한 두 수 중 하나가 답이 된다.
• 따라서 절댓값 기준으로 원래 수를 정렬하고, 인접한 두 수의 합을 구하다보면 반드시 0에 가장 가까운 합을 만드는 두 수를 찾을 수 있다-

---