[Java] BOJ 2470 두 용액

[Java] BOJ 2470 두 용액

 

www.acmicpc.net/problem/2470

2470번: 두 용액

 

package Baekjoon;

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

public class BOJ_2470_두용액 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		long[] nums = new long[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			nums[i] = Long.parseLong(st.nextToken());
		}
		Arrays.sort(nums);
		
		int head = 0, tail = N-1;
		long MIN = Long.MAX_VALUE;
		long val1 = 0, val2 = 0;
		long SUM;
		do {
			if(head >= tail) break;
			SUM = nums[head] + nums[tail];

//			if(Math.abs(SUM) > MIN) break;
			if(MIN > Math.abs(SUM)) {
				MIN = Math.abs(SUM);
				val1 = nums[head];
				val2 = nums[tail];
			}
			if(MIN == 0) break;
			else if(SUM > 0) tail--;
			else if(SUM < 0) head++;
		} while(true);
		
		System.out.println(val1 + " " + val2);
	} // main
	
}

 

소요시간 36분

이분탐색 문제라는 걸 듣고 풀어버렸다.... ㅎ

 

 

일단 숫자배열을 오름차순으로 정렬후에

head 를 0에 tail을 N-1 에 둔다.

 

더했을 때 0에 가까우려면, 더한 값이 음수일 땐 작은 숫자가 커져야 하고 더한 값이 양수일 땐 큰 숫자가 작아져야 한다.

 

그러므로

둘을 더해서 값이 음수라면 head 를 하나 올린다.

둘을 더해서 값이 양수라면 tail 을 하나 줄인다.

 

이렇게 양 쪽 끝에서 인덱스를 줄이는데

둘을 더한값의 절댓값을 MIN 과 비교하여 제일 작은 값을 저장하고 그때의 nums[head], nums[tail]을 저장해놓는다.

 

이미 MIN이 0일 때 혹은 head가 tail보다 더 큰 상황이 오면 모든 상황을 비교한 것이므로 종료한다.

 

실수를 여러가지해서 고치느라 힘들었다.

실수 중 하나는 위 코드의 주석 부분을 넣어서 끝나게 해버린 점...

SUM이 MIN보다 커도 더 진행했을 때 더 작은 값을 찾을 수 있으니 break 해버리면 안 된다.