[백준] G5 2470번 두 용액 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

2470번: 두 용액

[문제] 

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다.  산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 

예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

[입력]

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

[출력]

첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

 

 

---

[풀이]

1. 입력받은 용액을 오름차순 정렬해준다.

2. 투포인터를 사용하여 왼쪽과 오른쪽 포인터를 사용해 각 값에 접근을 해주고 해당 값들의 합을 구한다.

3. 합이 이전에 저장된 합보다 크다면 넘어가고, 작다면 갱신해준다.

4. 합의 값이 0보다 작다면 왼쪽 포인터를 증가시키고, 아니라면 오른쪽 포인터를 감소시킨다.

5. 포인터가 서로 만나게 되면 종료하고 결과를 출력한다.

[접근]

1. 오름차순으로 정렬을 해두고 각 끝에서부터 합을 구하면서 비교했을 때의 최소를 구하면 되겠다고 생각하였다.

2. 그래서 투 포인터를 사용해 문제를 풀었다.

[코드]

package BOJ_gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main_G5_2470 {
	static int n;
	static int a; // 1번 용액
	static int b; // 2번 용액
	static int gap = Integer.MAX_VALUE; // 용액의 차이 (저장해두고 비교)
	static int sum; // 용액의 차이 (매번 갱신됨)
	static int arr[]; // 용액을 담을 배열

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		
		arr = new int[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// 용액 입력 받기
		for (int left = 0; left < n; left++) {
			arr[left] = Integer.parseInt(st.nextToken());
		}
		// 정렬
		Arrays.sort(arr);
		
		// 왼쪽 포인터와 오른쪽 포인터
		int left = 0;
		int right = arr.length - 1;
		
		// 왼쪽이 오른쪽보다 커지면 종료시킨다. (== 서로 만나게 되면 종료된다.)
		while (left < right) {
			// 절대값으로 두 용액의 합을 구해준다.
			sum = Math.abs(arr[left] + arr[right]);
			// 저장되어 있는 용액의 차이보다 작다면 == 0에 가깝다면
			if (sum < gap) {
				// 갱신
				gap = sum;
				a = arr[left];
				b = arr[right];
			}
			// 합이 0보다 작다면 왼쪽포인터 이동, 아니면 오른쪽 포인터 이동
			// sum으로 처리 안하는 이유 : sum은 abs로 절대값이기 때문에 무조건 0이상이다.
			if (arr[left] + arr[right] < 0)
				left++;
			else
				right--;
		}
		
		System.out.println(a + " " + b);
	}
}