[백준/JAVA] 2467_용액

백준🔗

2467번: 용액

 

 

문제

 

 

 

간단 풀이

탐색을 할 때 "정렬이 되어 있다" 라는 조건이 있으면 무조건 이진 탐색이 순차적인 탐색보다 좋다!

따라서 용액의 특성값들이 오름차순으로 주어진다는 조건이 있기 때문에 이진 탐색으로 접근했다.

선택할 용액의 2개 중 하나는 첫번째 것부터 순서대로 고정시켜 두고, 나머지 1개의 용액을 앞서 선택한 1개의 용액보다 특성값이 큰 용액들 중에서 하나를 선택하도록 했다. 이 나머지 1개의 용액을 찾을 때 이진탐색을 활용했다.

 

이 때, 이진탐색이 끝나지 않았어도 중간중간 특성값이 0에 더 가까운 용액을 만들었을 때마다 해당 정보들을 저장할 수 있도록 했다. 

 

특성값은 절댓값이 10억을 넘지 않기 때문에 두 용액의 특성값 합도 20억 이내이므로 int형 범위 안에 들어온다.

 

 

코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		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());
		}
		int[] res = new int[2];
		int sum = Integer.MAX_VALUE;
		here: for (int i = 0; i < N - 1; i++) {
			int start = i + 1;
			int end = N - 1;
			int mid = 0;
			while (start <= end) {
				mid = (start + end) / 2;
				if (arr[i] + arr[mid] < 0) {
					start = mid + 1;
				} else if (arr[i] + arr[mid] > 0) {
					end = mid - 1;
				} else {
					res[0] = arr[i];
					res[1] = arr[mid];
					break here;
				}
				if (Math.abs(arr[i] + arr[mid]) <= sum) {
					sum = Math.abs(arr[i] + arr[mid]);
					res[0] = arr[i];
					res[1] = arr[mid];
				}
			}
		}
		System.out.println(res[0] + " " + res[1]);
	}
}

 

 

참고 자료