백준 2467: 용액(java)

문제

---

풀이

 

투 포인터와 이분 탐색을 이용하는 문제이다.

 

알고리즘은 아래와 같다.

1. left = 0, right = N-1
2. while(left < right):
3.    sum = sols[left] + sols[right]
4.    if(abs(sum) < min):
5.        min = abs(sum)
6.        res_left = left, res_right = right    //res_left, res_right는 현재까지 가장 0에 가까운 용액을 만들어내는 특성값
7.    if(sum > 0):    //합이 양수라면 더 작은 sols[right]에 대해 sum이 0에 더 가까워질 가능성 有
8.       right --
9.    else:    //합이 음수일 때도 마찬가지
10.    left ++

 

전체 코드

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

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[] sols=new int[N];
		
		for(int i=0; i<N; i++) {
			sols[i]=Integer.parseInt(st.nextToken());
		}

		int min=Integer.MAX_VALUE;
		int leftRes=0, rightRes=0;
		int left=0, right=N-1;
		
		while(left<right) {
			int sum=sols[left]+sols[right];
			
			if(min>Math.abs(sum)) {
				min=Math.abs(sum);
				leftRes=left;	rightRes=right;
			}
			//binary search
			if(sum>=0) {
				right--;
			}
			else {
				left++;
			}
		}
		
		System.out.println(sols[leftRes]+" "+sols[rightRes]);
	}
}