[백준 2470]두 용액 2️⃣

2470번: 두 용액

산성용액 특성값 : 1 ~ 10억 ( 양의 ) 정수

알칼리 용액 특성값 : -1 ~ -10억 (음의) 정수

같은 양의 두 용액을 혼합한 용액의 특성값 : 각 용액의 특성값의 합.

특성값이 0에 가장 가까운 용액을 만들려고 한다.

둘 다 알칼리성 이거나, 둘 다 산성 인 경우가 0 에 가장 가까운 경우일 수도 있다

-100 -55 1 2 10 이라면 “1””2”를 뽑는게 가장 0에 가깝겠다

6
-60 -55 50 65 67 70

문제풀이

이 문제는 투 포인터로 풀어야 할 듯 하다

두 수의 합의 절댓값이 0에 가장 가까운 경우를 뽑아내야 한다.

모든 수들은 10억 이하이고, 두 수의 합을 구하는 것이기에 int 형으로 커버 가능하다.

• 양 쪽에 Left, right 라는 포인터를 두고, 이를 이동시키며 절댓값이 최소가 되는 값을 찾는다

첫 번째로 생각했던 것은 그냥

1. left < right 일 때 까지 반복한다
   1. left + right 가 음수 → left 를 이동
   2. left + right 가 0 → stop
   3. left + right 가 양수 → right 를 이동
   4. 이동한 결과가 이전의 min 보다 커지면 → stop

으로 했다.

이 경우 생기는 문제점 : 아래의 경우 답(1,2) 를 구하지 못한다. 왜냐하면 “d번 조건에 걸려" : left 가 -55 → 1 로 넘어갈 때, 이동한 결과(1,40 → 41) 이 이전의 min(-55, 40 → 15) 보다 커지기 때문이다.

5
-60 -55 1 2 40

n 이 10만이기 때문에 전체를 돌아도 괜찮다고 생각했다. 따라서 4번 조건은 없애주었다.

참고로, 여기에서 left + right 가 0 일 때는 바로 break 를 해줘야만 한다. 그렇지 않으면 시간초과가 뜨도록 되어있는 것 같다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static int n;
	public static int[] arr;
	public static int[] ans = new int[2];

	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static StringTokenizer st;

	public static void setUp() throws IOException {
		n = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		arr = new int[n];

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(arr);

	}

	public static void solve() {
		int left = 0, right = n - 1;
		int min = Integer.MAX_VALUE;
		int temp = 0, abs = 0;
		// 두 수의 합이 0 -> stop
		// 두 수의 합이 음수 -> left 를 움직임
		// 두 수의 합이 양수 -> right 를 움직임
		while (left < right) {
			temp = arr[left] + arr[right];
			abs = Math.abs(temp);
			if (abs == 0) {
				ans[0] = arr[left];
				ans[1] = arr[right];
				break;
			}
			if (abs < min) {
				min = abs;
				ans[0] = arr[left];
				ans[1] = arr[right];
			}
			if (temp < 0)
				left++;
			else if (temp > 0)
				right--;
		}
	}

	public static void main(String[] args) throws IOException {
		setUp();
		solve();
		bw.write(ans[0]+" "+ans[1]);
		bw.flush();
		br.close();
		bw.close();
	}
}