[백준] 2467 용액 / 자바(Java)

문제

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

2467번: 용액

 

---

해설

정렬되어 있는 수들 중 2개의 값의 합이 가장 0에 가까운 수의 조합을 찾는 문제이다.

 

모든 수의 조합을 확인하려면 100,000 * 99,999가 되어 너무 많은 조합을 확인해야하므로 

배열에서 2개의 포인터를 사용해 원하는 조건에 맞춰 확인하는 방식을 사용한다.

 

입력값은 오름차순으로 정렬되어 있으므로 입력을 배열로 변경한다면 왼쪽에는 가장 작은 수, 오른쪽에는 가장 큰 수가 있을 것이다.

두 수의 합을 시작으로 만약 그 합이 0보다 작다면 왼쪽에서 한칸 더 진행해 그 다음으로 작은 수로, 합이 0보다 크다면 오른쪽에서 한칸 더 진행해 그 다음으로 큰 수를 합하여 비교한다. 이를 두 수가 겹칠 때 까지 반복하면 조건에 맞는 값을 모든 조합을 확인하는 것보다 더 빠르게 발견할 수 있다.

 

왼쪽 값의 위치를 저장할 포인터로 left, 오른쪽 값의 위치를 저장할 포인터로 right로 정하고 둘을 비교하는 while문의 조건을 left가 right보다 작을 때로 둔다면 간단하게 해결이 가능하다. 

주의점

• 수의 범위가 -1,000,000,000 ~ 1,000,000,000으로 크고 N의 값은 100,000이다
• 두 종류의 용액이 정렬되어 나온다
• 한가지 종류의 용액만이 나올 수 도 있다.

코드

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 NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		long input[] = new long[N];
		StringTokenizer st = new StringTokenizer(br.readLine());

		for(int i=0;i<N;i++) {
			input[i]=Long.parseLong(st.nextToken());
		}
		
		int left=0;
		int right=N-1;
		int minans=0,maxans=0;
		long min = Long.MAX_VALUE;
		while(left<right) {
			long sum = input[left]+input[right];
			if(min>Math.abs(sum)) {
				min = Math.abs(sum);
				minans=left;
				maxans=right;
			}
			if(sum>=0) {
				right--;
			}else {
				left++;
			}
		}
		
		System.out.println(input[minans]+" "+input[maxans]);
		
	}
}