BOJ - 2470 ) 두 용액
https://www.acmicpc.net/problem/2470
2470번: 두 용액
첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.
www.acmicpc.net
두 용액은 이전 포스트
https://algorithmstudy-mju.tistory.com/120
BOJ - 2003 ) 수들의 합 2
https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각..
algorithmstudy-mju.tistory.com
에서 다루었던 유형중 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);
}
}
