링크

문제 링크

문제 설명

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.

예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

입력

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

출력

첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

입출력 예제

풀이

1. 투포인터 알고리즘으로 왼쪽은 제일 작은값과 오른쪽의 가장 큰 값의 차이를 비교하면서 O(n)을 노린다.
2. 그러기 위해서는 정렬을 해야한다.
3. 아 그리고 입력을 Scanner로 받으면 안된다! BufferedReader, StringTokenizer를 쓰자
4. 정렬 후에는 left가 right을 넘을 때까지 둘 간의 차이가 0에 더 가까운 값이 나온다면 갱신해주고 둘의 합이 양수라면 right-- 음수라면 left++을 하면서 좁혀준다.

로직은 빨리 구현했는데 자꾸 시간초과가 나는것이다...

예제 케이스는 모두 맞는 상황이었기 때문에 다른 문제가 있나 싶어서 블로그를 서칭하기 시작했다.

과장 하나도없이 나랑 변수 이름 말고 전부 똑같은 코드를 발견했고, 그 코드 역시 Scanner로 입력을 받고 통과되었길래 Scanner 문제도 간과하였다.

그러나 같은 로직의 코드를 C++로는 너무 자연스럽게 통과하는 것을 보고 입력을 바꾸기로 하였다.

바꿨더니 바로 통과...!!

코드

package Sample;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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());
		String s = br.readLine();
		StringTokenizer st = new StringTokenizer(s, " ");
		int[] arr = new int[N];
		for(int i = 0; i < N; i++) 
		{
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);
		int res = Integer.MAX_VALUE;
		int start = 0;
		int end = arr.length - 1;
		int answer1 = 0;
		int answer2 = 0;
		while(start < end) {
			int temp = Math.abs(arr[start] + arr[end]);
			if(res > temp) {
				answer1 = arr[start];
				answer2 = arr[end];
				res = temp;
				if(temp == 0) break;
			}
			if(arr[start] + arr[end] > 0)
				end--;
			else
				start++;
		}
		System.out.println(answer1 + " " + answer2);
	}
}