백준 2470번. 두 용액 (Java)

문제 링크 : https://www.acmicpc.net/problem/2470

합이 0에 가장 가까운 두 용액을 구하는 문제입니다.

N이 최대 100,000 인데 시간제한 1초인데다가 언어별 추가시간이 없기 때문에 O(n)으로 풀어야 합니다.

비효율적으로 푸는 방법은 N개중에서 2개를 뽑는 콤비네이션을 완전탐색으로 돌려서 푸는 방법이 있긴 합니다.

O(N)에 푸는 방법은 우선 배열을 정렬합니다.

그다음 가장 가장 작은 숫자인 arr[0]과 가장 큰 숫자인 arr[n-1]을 더한 후에 max 값과 비교합니다.

만약에 두 숫자의 합이 0보다 크다면 arr[n-1]의 절대값이 arr[0]보다 더 크기때문에 arr[n-1]의 인덱스를 하나 줄여줍니다.

반대로 두 숫자의 합이 0보다 작다면 arr[0]의 인덱스를 하나 증가시킵니다.

이렇게 배열의 양쪽 끝에서부터 서로 줄여가면서 합이 0에 가장 가까운 숫자를 구하면 됩니다.