BOJ - 2470 ) 두 용액

---

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

2470번: 두 용액

 

---

두 용액은 이전 포스트 

 

https://algorithmstudy-mju.tistory.com/120

BOJ - 2003 ) 수들의 합 2

에서 다루었던 유형중 2번째에 해당되는 내용이다. 긴 배열에서 

 

특정 구간에 반복접근하여서 ( 용액 두개 선정 ) 답을 찾아가는 과정이므로 투 포인터로 해결할 수있다.

 

정렬한 후 ( -MAX ~ MAX )값에서 양끝값 ( S ,E )에서 더한값이

 

음수이면 S 값을 증가시켜서 전체값을 증가시키고 

양수이면 E값을 감소시켜 전체의 값을 감소시킨다.

 

이러한 작없을 교차하는 S < E 까지 반복하면, 원하는 0 과 거리가 최소인 두 점을 구할 수 있다.

 

---

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

public class 두용액 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int num[] = new int[n];
		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < n ; i++) num[i] = Integer.parseInt(st.nextToken());
		Arrays.sort(num);
		int from , to , res  ;
		from = num[0] ; to = num[n-1];
		res = Math.abs(num[0] + num[n-1]);
		for(int s = 0 , e = n -1; s < e ;) {
			int mid = num[s] + num[e];
			if(Math.abs(mid) < Math.abs(res)) {
				res = Math.abs(mid);
				from = num[s] ; to = num[e];
				if(mid == 0) break;
			} else if( mid > 0) {
				e--;
			} else if (mid < 0) {
				s++;
			}
		}
		System.out.println(from + " " + to);
	}

}

---

중간에 0 이되는 경우의 수를 발견한다면 , 그 뒤는 볼 필요가 없다..!