[PS] 백준 2467 - 용액

문제

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

2467번: 용액

 

해설

문제를 빠르게 해결하기 위해서는 문제 설명이 터무니없이 길다거나 익숙하지 않은 단어가 있을 때 문제 해결에 도움을 줄 수 있는 핵심 키워드를 뽑아내는 것이 중요합니다.

 

이 문제의 경우 과학 - 산성 - 알칼리성 등 혼란을 주기 위한 장치들이 심어져 있지만 그중 핵심을 찾아 요약해보겠습니다.

 

1. 용액의 특성 값들이 주어진다.

2. 두 용액을 혼합하여 특성 값이 0에 가장 가까운 용액을 만드려고 한다.

3. 음수의 값을 갖는 용액만이 주어질 수 도 있고, 양수의 값을 갖는 용액들만이 주어질 수 도 있다.(예외)

4. 이 중 더했을 때 특성 값이 0에 가장 가까운 두 용액을 출력한다.

 

 

다음으로 문제를 파악한 뒤엔 적절한 자료구조와 알고리즘을 선택해야 합니다.

 

먼저 입력 범위를 살펴보면 0을 제외한 -1,000,000,000부터 1,000,000,000까지이므로 이는 정수형 변수 Int의 할당 범위를 넘지 않기 때문에 정수형 배열만으로 입력을 받을 수 있습니다.

 

다음으로 두 용액을 더했을 때 최소가 되는 경우를 찾아야 하므로 이중 포문을 먼저 생각해볼 수 있습니다.

하지만 시간 복잡도를 고려해보면 O(N^2)이고 최악의 입력이 100,000이라고 가정했을 때 문제의 시간제한 1초를 넘어가므로 이 알고리즘으로 해결하는 것은 불가능하다는 것을 알 수 있습니다.

 

다른 선형 탐색 중 O(NlogN)의 시간 복잡도를 갖는 이진 탐색을 활용한다면 문제를 해결할 수 있을 것 같습니다. 이진 탐색의 구현 방법은 검색을 통해 쉽게 찾을 수 있기 때문에 알고리즘에 대한 설명은 생략하겠습니다.

 

 

문제 해결을 위한 설계가 어느 정도 되었으니 구현부로 넘어가 보겠습니다.

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

/**
 * @memory 	32860KB / 128MB
 * @time   		288ms / 1초
 */
public class BOJ_G5_2467_용액 {
	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());
		}
		br.close();

		int min = Integer.MAX_VALUE;
		int t1 = 0, t2 = 0;
		for (int i = 0; i < n; ++i) {
			// 자신 기준 오른쪽 용액을 대상으로 이진탐색
			int a = i+1, b = n-1;
			while (a <= b) {
				int m = (a+b)/2;
				int v = Math.abs(arr[i] + arr[m]);
				// 최소가 되는 특성 값을 찾았다면 갱신
				if (min > v) {
					min = v;
					t1 = arr[i];
					t2 = arr[m];
				}
				/* 이 문제의 목적은 자신과 더했을 때 
				 * 절댓값이 0이 나오는 가장 가까운 위치를 찾는 것입니다.
				 * 따라서 '자신의 값에 대한 음의 값'과 가장 가까운 위치를 찾는다면
				 * 0과 근사한 결과를 얻을 수 있습니다.
				 */
				if (arr[m] == -arr[i]) {
					break;
				} else if (arr[m] < -arr[i]) {
					a = m+1;
				} else {
					b = m-1;
				}
			}
		}
		System.out.printf("%d %d", t1, t2);
	}
}

 

코드를 살펴보면 이진 탐색의 범위가 자신(i) 기준 오른쪽인 것을 알 수 있습니다. 이는 문제의 예제 입력이 '-99 -2 -1 4 98' 일 때 -99와 최소를 이루는 값이 98이고 98의 최소를 이루는 값이 -99이므로 결과 쌍은 동일하기 때문에 이전에 확인한 범위를 중복으로 체크하지 않기 위함입니다.

 

다음으로 이진 탐색 중 최소가 되는 특성 값을 찾았을 때 그 값들을 갱신해줍니다.

 

마지막으로 범위 갱신 부분을 살펴보면 이 문제의 목적이 자신(i)과 더했을 때 0과 가장 가까운 위치를 찾는 것이므로 '자신의 값에 대한 음의 값'과 가장 가까운 위치를 찾는다면 0과 근사한 결과를 얻을 수 있습니다.