[BaekJoon] 2467 용액

1.  문제 링크

https://www.acmicpc.net/problem/2467

2.  문제

요약

• 각 용액은 특성을 나타내는 하나의 정수를 갖는데 산성 용액은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액은 -1부터 -1,000,000,000까지의 음의 정수로 나타냅니다.
• 같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의하는데, 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만드려고 합니다.
• 산성 용액과 알칼리성 용액의 정렬된 특성값이 주어질 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 문제입니다.
• 입력: 첫 번째 줄에 2 이상 100,000 이하의 정수인 용액의 수 N이 주어지고 두 번째 줄에는 -1,000,000,000 이상 1,000,000,000 이하인 용액의 특성값 N개의 정수가 오름차순으로 입력됩니다.
  * 모든 용액의 특성값들은 서로 다릅니다.
• 출력: 첫 번째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 오름차순으로 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Main {
	public int[] getNearZero(int[] solution) {
		int[] result = new int[2];
		long min = Long.MAX_VALUE;
		Arrays.sort(solution);
		int left = 0;
		int right = solution.length - 1;
		int al = 0;
		int ar = solution.length - 1;
		while(left <= right) {
			long sum = (long)solution[right] + solution[left];
			if(left != right && Math.abs(sum) < min) {
				al = left;
				ar = right;
				min = Math.abs(sum);
			}
			if(sum >= 0) {
				right--;
			} else {
				left++;
			}
		}
		result[0] = solution[al];
		result[1] = solution[ar];
		return result;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		int[] solution = new int[num];
		String[] input = br.readLine().split(" ");
		br.close();
		for(int i = 0; i < num; i++) {
			solution[i] = Integer.parseInt(input[i]);
		}
		Main m = new Main();
		int[] result = m.getNearZero(solution);
		for(int i = 0; i < result.length; i++) {
			bw.write(result[i] + " ");
		}
		bw.flush();
		bw.close();
	}
}

4.  접근

• 이 문제는 투 포인터를 이용하여 혼합하였을 때 특성값이 0에 가장 가까운 용액을 찾는 문제입니다.
• 주어진 정렬된 특성값에서 가장 작은 특성값과 가장 큰 특성값 2개로 먼저 시작하여 두 용액을 혼합했을 때의 특성값을 구하고 해당 특성값의 절댓값이 이전에 구했던 특성값보다 작다면, 즉 0에 가깝다면 해당 값을 0에 가장 가까운 용액의 후보로 합니다.
• 만약 두 용액을 혼합했을 때의 특성값이 0보다 크거나 같다면 0에 더욱 가까워지기 위해 값을 줄여야 하므로 오른쪽 포인터를 왼쪽으로 이동시킵니다.
• 두 용액을 혼합했을 때의 특성값이 0보다 작다면 0에 더욱 가까워지기 위해 값을 키워야 하므로 왼쪽 포인터를 오른쪽으로 이동시킵니다.

1. 두 용액을 혼합했을 때 가장 0에 가까운 특성값을 저장할 min 변수를 만들고 초기값은 처음 나오는 용액의 합보다 무조건 커야하므로 long 타입의 가장 큰 수로 지정합니다.
2. 왼쪽 포인터를 0, 오른쪽 포인터를 (용액의 개수 - 1)로 초기값을 설정하고 두 용액을 혼합했을 때 가장 0에 가까운 특성값을 갖는 두 용액의 index를 저장할 al, ar 변수를 생성합니다. al은 왼쪽 포인터에서의 index, ar은 오른쪽 포인터에서의 index를 의미합니다.
3. 왼쪽 포인터 값이 오른쪽 포인터 값과 만날 때까지 반복문을 돌며 혼합했을 때 특성값이 0에 가장 가까운 두 용액을 찾아냅니다.
   1. 현재 왼쪽 포인터와 오른쪽 포인터에 해당하는 두 용액을 혼합했을 때의 특성값을 구합니다.
   2. 아직 왼쪽 포인터가 오른쪽 포인터와 만나지 않았고 해당 특성값의 절댓값이 이전 특성값의 절댓값(min 변수값)보다 작다면 min 변수의 값을 현재 구한 특성값의 절댓값으로 변경하고 al과 ar 두 변수 또한 al은 현재 왼쪽 포인터의 값으로, ar은 현재 오른쪽 포인터의 값으로 변경합니다.
   3. 만약 현재 구한 두 용액을 혼합했을 때의 특성값이 0보다 크거나 같다면 값을 줄여야하므로 오른쪽 포인터를 왼쪽으로 1 이동시킵니다.
   4. 만약 현재 구한 두 용액을 혼합했을 때의 특성값이 0보다 작다면 값을 키워야 하므로 왼쪽 포인터를 오른쪽으로 1 이동시킵니다.
4. 3번에서 왼쪽 포인터가 오른쪽 포인터를 넘어 반복문이 끝났을 때의 al과 ar의 값이 각각 두 용액을 혼합했을 때 가장 0에 가까운 용액들의 index를 가리키고 있고 왼쪽 포인터의 값을 나타내는 al의 특성값이 오른쪽 포인터의 값을 나타내는 ar의 특성값보다 작기 때문에 al의 특성값을 먼저 출력해주고 ar의 특성값을 출력합니다.