[JAVA] BOJ(백준) - 두 용액 - 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에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

입력

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

출력

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

---

문제 접근 방법

문제를 풀기전에 투포인터 알고리즘에 대해 먼저 알아야 한다.

간단하게 설명하자면 정렬된 배열(리스트)가 있을때 요소값 두개를 갖고 특정값을 찾아내는 알고리즘이다.

이때 요소 두개를 가리키는 인덱스 두개가 존재하고 이를 투포인터라 한다.

투포인터 알고리즘에 대한 자세한 내용은 https://benn.tistory.com/9 이분 블로그에서 참고하면 될듯 하다.

 

접근 순서

1. 포인터 생성
   투포인터 문제를 풀때 무조건 포인터가 두가지 필요하다.
   이때 두개의 포인터 시작점을 하나는 가장앞, 하나는 가장뒤에서 시작하도록 했다.
   
   
2. 반복문
   포인터를 가장앞과 뒤에서 시작하는 이유는 0에 최대한 가까운 값을 찾아야 하기 때문에 두개의 포인터를 모두 앞에서 시작하는 것보다 앞과 뒤에서 시작하도록 했다.
   또한 두 개의 포인터를 이용한 계산결과를 특정값과 비교해 앞의 포인터는 늘리고 뒤의 포인터는 줄여가면서 특정값을 찾을때 까지 반복하거나 두개의 포인터가 만날때까지 반복하도록 하기 위해서이다.
   
   
3. 특정값(0)에 가장 가까운 값을 찾기
   특정값에 가까운 값을 찾는다는 말은 계산 결과에 따라 특정값이 나올수도 안나올수도 있다는 말이다.
   따라서 현재 계산한 결과(sum)를 이전에 계산한 결과(min)와 비교해 특정값에 더 가까운 결과의 정보를 저장해 줄수 있는 변수가 필요하다 생각했다.

 

문제 풀이시 주의 해야할것

• 정렬
  일단 입력값이 정렬이 안돼있기 때문에 투포인터 사용을 위해선 정렬을 해야한다.
  이때 입력받는 최대 데이터의 개수가 100,000이기 때문에 O(N^2) 보다 아래의 시간복잡도를 갖고있는 정렬을 해야겠다고 생각하여 Arrays.sort()대신 리스트를 이용해 Collections.sort()를 이용했다.
  
  Arrays.sort() -> 최악 O(N^2)
  Collections.sort() -> 최악 O(NlogN)
• 출력
  오름차순으로 출력해야하는데 어차피 정렬된 리스트를 두개의 포인터가 양끝에서부터 시작하기 때문에
  출력도 알아서 정렬돼 있다.
  
  
• 절댓값
  이문제는 특정값 0에 가까운 값을 뽑는 문제이다.
  따라서 결과값이 "-" 일때를 제외하기 위해 이전 결과값과 현재 결과값을 비교할때 절댓값을 씌워 비교를한다.
  이렇게 되면 절댓값 씌우기 전이 마이너스든 플러스든 절댓값 씌운 더 작은 값이 0에 더 가까운 수 가된다.

자세한 내용은 코드를 보며 이해해보자.

---

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
	static ArrayList<Integer> list = new ArrayList<Integer>();//용액들
	static int min = Integer.MAX_VALUE;//0에 가까운 최소값(이전 결과값)
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());//용액 개수
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			list.add(Integer.parseInt(st.nextToken()));
		}
		
		//오름차순 정렬
		Collections.sort(list, new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {
				if(o1<o2) return -1;
				else if(o1>o2) return 1;
				else return 0;
			}
		});
		
		System.out.println(findLiquid());//출력
		
	}
	
	//0에 가까워지는 용액 2개 찾기
	public static String findLiquid() {
		//1.포인터 생성
		int start = 0;//첫번째 인덱스
		int end = list.size()-1;//두번째 인덱스
		int minStart = 0;//정답 인덱스(첫번째)
		int minEnd = 0;//정답 인덱스(두번째)
		int sum = 0;//두용액의 합
		
		//2.반복문
		while(start<end) {//두 용액의 인덱스가 만날때까지 돌리기
			sum = list.get(start) + list.get(end);//현재 결과값
			
			//최소값이 sum보다 크면 min의 정보를 sum의 정보로 갱신 시켜주기
			//절대값 쓰는 이유는 0에 가까운 최소값을 구하기 위해선
			//계속 양수랑 비교해줘야함.
			if(Math.abs(min)>Math.abs(sum)) {
				min = sum;
				if(min==0) return list.get(start)+" "+list.get(end);//최소값0이면 바로 끝내기
				minStart = start;//최소값 인덱스 갱신
				minEnd = end;//최소값 인덱스 갱신
			}
			
			//특정값 0을 기준으로 인덱스를 늘리고 줄이기. 
			if(sum>0) end--;
			else if(sum<0) start++;
		}
		
		return list.get(minStart)+" "+list.get(minEnd);
	}
}

---

마치며

요소 두개를 이용해 비교하는 방식은 완전탐색으로도 충분히 풀수 있는 문제지만 데이터 양이 방대해질 경우 완전탐색은 시간이 매우매우 오래걸릴 수도 있다. 

이에 대한 방안으로 투포인터를 이용한 탐색방법을 공부할 수 있었던 문제였다.