백준 2470 두 용액

문제

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

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

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

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

---

코드

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

        //n과 liquids 입력받기
        int n = Integer.parseInt(br.readLine());
        int[] liquids=new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            liquids[i] = Integer.parseInt(st.nextToken());

        //용액 오름차순 정렬
        Arrays.sort(liquids);
        
        //모든 용액을 돌면서 이진탐색으로 정답 갱신
        int[] answer=new int[]{liquids[0], liquids[1]};
        for(int i:liquids){
            int another=liquids[binarySearch(liquids, i)];
            
            //이진 탐색의 결과가 자기 자신과 같으면 continue
            if(another==i)
                continue;

            if(i +another==0){
                answer=new int[]{Math.min(i, another), Math.max(i, another)};
                break;
            }

            if(Math.abs(answer[0]+answer[1])>Math.abs(i +another))
                answer = new int[]{Math.min(i, another), Math.max(i, another)};
        }

        System.out.println(answer[0]+" "+answer[1]);
    }

    //이진 탐색
    public static int binarySearch(int[] array, int liquid){
        int start=0;
        int end=array.length;

        int answer=0;
        while(start<end){
            int mid=(start+end)/2;

            //현재 용액과 mid 용액을 섞었을 때 0보다 크다면 mid를 줄여야 함 
            if(liquid+array[mid]>0){
                end=mid;

                //answer 갱신
                if(Math.abs(array[answer]+liquid)>Math.abs(array[mid]+liquid))
                    answer=mid;
            }
            if(liquid+array[mid]==0){
                return mid;
            }
            if(liquid+array[mid]<0){
                start=mid+1;

                if(Math.abs(array[answer]+liquid)>Math.abs(array[mid]+liquid))
                    answer=mid;
            }
        }

        return answer;
    }
}

---

해결 과정

1. 모든 용액을 정렬해두고, 두 용액의 합이 0에 가까워지도록 하는 값을 이진 탐색으로 찾았다. 0번~(N-1)번 용액과 더했을 때 가장 0에 가까운 값을 만드는 용액이 이진 탐색의 리턴 값이다. 다만 자기 자신과 같은 용액은 정답을 갱신하지 않도록 했다.

   ex) 1, 2, 3, 4, 5가 있을 때
   1에 대해서 이진탐색하면 1이 나온다. 1+1=2 가 0에 가장 가깝기 때문이다.
   하지만 자기 자신이므로 continue
   2에 대해서 이진탐색하면 1이 나온다. 1+2=3이 최적의 답이다.

2. 😁