[백준 / BOJ] 2470번 : 두 용액 - JAVA

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

2470번: 두 용액

이분 탐색

용액의 특성값을 정렬한 뒤, 두 개의 용액을 양 끝에서부터 더해보면 되므로 이분 탐색으로 풀었다. start와 end 값을 더한 절대값의 최소값을 찾기 위해 min이라는 변수를 두고, 항상 절대값으로만 비교하도록 했다.

 

물론 위 코드로도 답을 찾을 수 있지만 용액의 특성값이 모두 음수, 혹은 모두 양수인 경우에는 굳이 이분 탐색을 돌릴 필요가 없기 때문에 따로 조건문을 추가했다. (그런데 백준에서 돌렸을 때 조건문이 없는 버전이 더 빠르고 메모리도 적게 써서 의문이다)

 

전체 코드

// 시간 : 280ms
// 메모리 : 31288KB
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());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int[] liquid = new int[N];
		
		for (int i = 0; i < N; i++) {
			liquid[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(liquid);
		
		if(liquid[0] > 0) {
			System.out.println(liquid[0] + " " + liquid[1]);
			return;
		} else if(liquid[N - 1] < 0) {
			System.out.println(liquid[N - 2] + " " + liquid[N - 1]);
			return;
		}
		
		int start = 0;
		int end = N - 1;
		int min = Integer.MAX_VALUE;
		
		int ans1 = 0;
		int ans2 = 0;
		
		while(start < end) {
			
			int sum = liquid[start] + liquid[end];
			if(Math.abs(sum) < min) {
				min = Math.abs(sum);
				ans1 = liquid[start];
				ans2 = liquid[end];
			}
			
			if(sum == 0) {
				ans1 = liquid[start];
				ans2 = liquid[end];
				break;
			} else if(sum > 0) {
				end--;
			} else {
				start++;
			}
		}
		
		System.out.println(ans1 + " " + ans2);
	}

}