[1. 문제 설명]
N 개의 정수로 이루어진 수열에서 두 원소의 합이 0에 가장 가까운 원소 한쌍을 오름 차순으로 출력
각 원소의 값은 모두 다르다.
[2. 풀이 접근]
수열이 모두 음수로 구성 된 경우, 가장 큰 값 두개를 더하면 되고,
수열이 모두 양수로 구성 된 경우, 가장 작은 값 두개를 더하면 된다.
수열이 양수와 음수로 구성 된 경우는 아래와 같이 접근할 수 있다.
먼저 전체 수열을 오름차순으로 정렬한다.
head 와 tail 을 각각 0 과 N-1 로 설정한다.
head 와 tail 을 적절히 움직이면서 탐색하는 것이다.
배열에 양 끝쪽에는 절대값이 가장 큰 값들이 온다.
head tail
<---- 음수 ........ 양수 ---->
탐색 과정은 아래와 같다.
두 원소의 합이 0이 된 경우는 더 이상 탐색 할 필요가 없다.
그러나, 두 원소의 합이 0 이 아닌 경우는 더 탐색해봐야 한다.
0 보다 큰 경우는 head 쪽 보다 tail 이 가리키는 값이 더 크다고 볼 수 있으므로,
tail 을 움직인다.
반대로 0 보다 작은 경우는 head 쪽 값이 tail 쪽 보다 더 작게 된다.
그래서 head 를 움직인다.
=== 다른 풀이 ===
두 수의 합이 0에 가깝다는 것은
부호가 다른 두 값이 절대값을 기준으로 정렬 했을 때, 서로 인접해 있다고 볼 수 있다.
그래서 먼저 수열을 절대값을 기준으로 오름차순 정렬한다.
이제 index 를 0에서 부터 N-2 까지 움직이면서
바로 옆에 있는 데이터와 더하면서 탐색해보면 된다.
정렬한 수열이 아래와 같을 때,
-3, -5 이면 -5 이후는 5와 절대값 6 이상이 되는 값만 올 수 있다. (문제 조건으로 인해)
-3 -5 4 이런 경우는 올 수 없다는 것이다.
-3 -5 5 인 경우는 -5 가 인접한 5와 더하면서 최소값을 업데이트 하게된다.
3 5 -5 인 경우는 3+5=8 이라서 3-5 까지 확인할 수는 있지만, 5-5=0 을 확인하게 되며, 0을 찾게되었으므로,
더 진행 할 필요는 없게 된다.
[3. 코드-A]
[3. 코드-B]