[BOJ] 백준 2467번 용액 (Java)

#2467 용액

난이도 : 골드 5

유형 : 이진탐색 / 투포인터

2467번: 용액

▸ 문제

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

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

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

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

▸ 입력

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

▸ 출력

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

 

문제 풀이  

두 수의 합이 0에 가까운 집합을 구하는 문제로 투 포인터 또는 이진탐색으로 풀이가 가능하다. 직관적인 접근 방법으로는 투포인터가 더 쉽다. 이진탐색은 경험을 위해 추가 풀이를 하였다.

 

투 포인터

입력 데이터는 오름차순으로 주어진다고 했으므로 따로 정렬을 해주지 않아도 된다. 첫 원소는 가장 작은 값이고, 끝 원소는 가장 큰 값이므로 투 포인터를 사용하여 서로 가운데로 향하여 움직이게 한 다음 가장 0에 가까운 수를 구해주면 된다.

1. 0과 n-1을 각 투포인터로 지정한다.
2. 투포인터를 사용하여 합이 0에 가까운 구간을 탐색한다.
   1. min > Math.abs(arr[left]+arr[right])  합이 0에 가장 가까운 값이 갱신되면 저장해준다.
   2. sum >=0   합이 0보다 크거나 같다면 더 작아져야 하므로 오른쪽 포인터를 이동한다.  right--;
   3. sum <0   합이 0보다 작다면 더 커져야 하므로 왼쪽 포인터를 이동한다. left--;

 

이진탐색

투 포인터와 아이디어는 같지만 탐색방식이 다르다. 하나의 원소(arr[i])를 픽한 다음에 나머지 원소 중 현재 원소*-1와 가장 가까운 원소를 이진탐색을 통해 찾아준다. 그래야 0에 가장 가까운 값을 찾을 수 있기 때문이다.

 

1. arr[i] 기준점을 뽑는다. 
2. [i+1 ~ n-1]구간에 있는 원소 중 arr[i]*-1와 가장 가까운 값을 이진탐색을 통해 탐색한다.
   1. min > Math.abs(arr[i]+arr[mid])  0에 가장 가까운 값이 갱신되면 저장해준다.
   2. arr[mid] >= -arr[i]   기준점*-1보다 크다면 위치를 right = mid -1;로 옮겨준다.
   3. arr[mid] < -arr[i]  기준점*-1보다 작다면 위치를 left=mid+1;로 옮겨준다.

 

 

투 포인터 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
		
		long[] arr = new long[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			arr[i] = Long.parseLong(st.nextToken());
		}
		
		int left =0;
		int right =n-1;
		int ml =0, mr = 0;
		long min = Long.MAX_VALUE;
		while(left<right) {
			long sum = arr[left]+arr[right];
			if(min > Math.abs(sum)) {
				min = Math.abs(sum);
				ml = left; mr = right;
			}
			if(sum>=0) {
				right--;	
			}else {
				left++;
			}
		}
		System.out.println(arr[ml] +" "+arr[mr]);
	}
}

 

이진탐색 풀이 코드 

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

public class Main {

	static int n;
	static long[] arr;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		arr = new long[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			arr[i] = Long.parseLong(st.nextToken());
		}
		
		long min = Long.MAX_VALUE;
		int ml =0, mr = 0;
		for(int i=0; i<n-1; i++) {
			int left =i+1;
			int right =n-1;
			while(left<=right) {
				int mid = (left+right)/2;
				long sum = Math.abs(arr[i]+arr[mid]);
				
				if(min > sum) {
					min = sum;
					ml = i; mr = mid;
				}
				if(arr[mid]>= -arr[i]) {
					right = mid-1;
				}else{
					left = mid+1;
				}
			}
		}
		System.out.println(arr[ml]+" "+arr[mr]);
	}
}