문제
접근
정렬과 투 포인터를 이용하여 풀었다.
주어진 배열을 정렬한 후, 시작과 끝점을 잡고 하나씩 옮기며 비교해나갔다.
가장 앞을 start, 뒤를 end라고 했을 때, 둘 중에 어떤 것을 옮길지 정해야 했다.
start+1과 end-1에 있는 수의 절대값을 비교하여 더 큰 쪽으로 이동해주었다.
예를 들어 start+1이 -98, end-1이 99이면, start는 그대로 두고, end를 99로 바꿔주는 식이다.
이런식으로 이동해주면 N개의 수가 있을 때 O(N)으로 모든 수를 확인할 수 있다.
진행하다보면 start+1과 end-1이 동일해지는 순간이 온다.(마지막에)
이 경우에는 start와 end를 비교하여 마찬가지로 큰 쪽을 교체하여 준다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def searchMinSum(arr):
if arr[0] >= 0:
return arr[0], arr[1]
if arr[-1] <= 0:
return arr[-2], arr[-1]
start = 0
end = len(arr) - 1
minSum = abs(arr[start] + arr[end])
minStart = start
minEnd = end
while True:
if start >= end:
break
if abs(arr[start+1]) > abs(arr[end - 1]):
start += 1
elif abs(arr[start+1]) < abs(arr[end - 1]):
end -= 1
else:
if abs(arr[start]) < abs(arr[end]):
end -= 1
else:
start += 1
if abs(arr[start] + arr[end]) < minSum:
minSum = abs(arr[start] + arr[end])
minStart = start
minEnd = end
return arr[minStart], arr[minEnd]
def main():
n = int(input())
arr = list(map(int, input().split(' ')))
arr.sort()
a, b = searchMinSum(arr)
print(a, b)
if __name__ == "__main__":
main()