[JAVA] 백준 2470 두 용액

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

2470번: 두 용액

 

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

 

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

 

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

 

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

 

 

문제 풀이 

 

 

- 양쪽 끝의 start, end가 가리키는 원소끼리 더하여 최대한 두 수의 합이 0에 가깝도록 두 포인터를 업데이트 

- sum이 0보다 작으면 두 수의 합이 더 커져야 0에 가까워지므로, start를 증가 

- sum이 0보다 크면 두 수의 합이 더 작아져야 0에 가까워지므로, end를 감소 

 

정답 

 

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

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());
        }
        
        Arrays.sort(arr);
        
        int start = 0;
        int end = arr.length-1;
        int min = Integer.MAX_VALUE; //현재까지 0에 가장 가까웠던 합 
        int ans[] = new int[2];
        
        while(start<end)
        {
            int sum = arr[start]+arr[end];
            
            if(min>Math.abs(sum))
            {
                min = Math.abs(sum);
                ans[0] = arr[start];
                ans[1] = arr[end];
                
                if(sum == 0)
                    break;
            }
            
            if(sum<0)
            {
                start++; //수가 더 커져야 하므로 start 증가
            }
            else
            {
                end--; //수가 더 작아져야 하므로 end 감소 
            }
            
        }
        System.out.println(ans[0]+" "+ans[1]);
    }
}