[BOJ] 백준 2470번 두 용액 (Java)

#2470 두 용액

난이도 : 골드 5

유형 : 투 포인터 / 파라메트릭 서치

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에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

 

문제 풀이  

해당 문제는 투 포인터 기법으로 풀이해주면 된다. 투 포인터는 주어진 배열을 두 개의 포인터를 조작하면서 원하는 것을 얻는 기법이다.

 

백준 2003번 수들의 합2의 문제는 두 개의 포인터가 같은 방향으로 탐색을 진행했다면 해당 문제는 각 양 끝에서 가운데 방향으로 탐색을 해줄 것이다.

 

파라메트릭 서치

주어진 배열에서 0에 가장 가까운 용액을 만들어 내는 추출해줘야 하기 때문에 먼저 배열을 정렬해준 후, 양쪽 끝에서 두 포인터를 이용하여 서로 중앙을 향해 거리를 좁혀지는 형태로 진행하면서 용액을 골라내주면 된다. 두 개 이상일 경우에는 아무거나 추출해주면 된다. 정렬해주는 이유는 두 용액의 합이 0보다 클 때는 합을 줄여줘야 하기 때문에 오른쪽에 위치한 포인터를 움직여주고, 0보다 작을 때는 합을 크게해줘야 하기 때문에 왼쪽의 포인터를 움직이게 하기 위해서이다.

 

주어진 범위 내에 원하는 값 또는 조건에 일치하는 값을 찾아야하므로 이분 탐색이 아닌 최적화 문제를 결정 문제로 바꿔 '파라메트릭 서치'를 사용할 것이다.

• 최적화 문제 : 두 개의 서로 다른 용액을 혼합하여 특성값이 최소인 용액은 얼마인가?
• 결정 문제 : 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들 수 있는가?

 

포인터 2개가 양끝에서 시작하여 반대로 진행

해당 배열 arr [-1, 4, 7, -99, -2]로 시뮬레이션을 돌려보자.

 

빨간색은 s이고, 파란색은 e인 두 포인터는 s는 맨 왼쪽 0에서 시작하고 e는 배열의 끝 n에서 탐색을 시작한다. arr[s]+arr[e]의 값을 구한 다음 0과 가까운 값을 구하면 된다.

 

arr[s]+arr[e] = -92 < 0 이므로 값이 더 커져야한다. 해당 배열은 오름차순으로 정렬했기 때문에 두 수의 합이 커지기 위해서 s의 포인터를 한 칸 움직여줘서 더 큰 값을 넣어준다.

s:0, e:4

 

arr[s]+arr[e] = 5 > 0 이므로 값이 더 작아져야 한다. 작은 값을 넣어주기 위해서는 e의 포인터를 움직여준다.

s:1, e:3

 

arr[s]+arr[e] = 2 > 0  이므로 값이 더 작아져야 하므로 위와 같이 e의 포인터를 움직여준다.

s:1, e:3

 

arr[s]+arr[e] = -3 < 0 이므로 이번엔 s를 움직여주자. 

s:1, e:2

 

그런데 start >= end이므로 더 이상 탐색이 불가능하므로 종료해준다.

 

☛ 답은 가장 0에 가까웠던 2로, 해당 구간에 속하는 두 용액 -2, 4가 된다.

 

풀이 코드 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		int[] arr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		int[] res = new int[2];
		int s=0, e=n-1, min=Integer.MAX_VALUE;
		Arrays.sort(arr);
		while(s < e) {
			int sum = arr[s]+arr[e];
			
			if(min> Math.abs(sum)) {
				min = Math.abs(sum);
				
				res[0] = arr[s];
				res[1] = arr[e];
				
				if(sum==0) break;
			}
			
			if(sum <0) s++;
			else e--;
		}
		
		System.out.println(res[0]+" "+res[1]);
		
		
		
	}
}