[BOJ 2470] 두 용액(java)

---

문제

두 용액

---

문제 해설

정수 2개를 더해 최대한 0에 가까운 수를 만들어 내는 문제입니다.
N <= 100,000 이므로 Nlog(N)이하를 만족하는 알고리즘을 구현해야 합니다.

저는 정렬된 배열을 포인터 2개를 사용하여 푸는 방식인 투포인터를 사용해 문제를 해결했습니다.

왜 배열을 정렬시켜야 하나?

• 배열을 정렬시키지 않으면 start포인터를 당길지, end 포인터를 당길지 정해줄 수 없기 때문에 결국엔 완전탐색을 이용해야 합니다. 그렇게 되면 시간초과가 날 것입니다.

풀이 방법은 다음과 같습니다.

1. 두 포인터를 만듭니다.(start, end)
2. 포인터가 현재 가리키는 인덱스의 배열값 두개를 합칩니다.
3. 합친 특성값이 현재 저장되어있는 최소 특성값과 비교하여 작다면 갱신시킵니다.
4. 이제 특성값을 더 줄일 수 있는 방법을 모색해야 하는데, start 인덱스의 값과 end 인덱스의 값 중 절대값이 더 큰 것을 움직입니다.
5. 2번으로 돌아갑니다.

---

풀이 코드

package 알고리즘스터디;

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

public class BOJ2470_두용액 {
	static int n, start, end;
	static int[] liquid;
	static int[] answer = new int[2];
	static int max = 2000000000;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n = Integer.parseInt(br.readLine());
		liquid = new int[n];
		st = new StringTokenizer(br.readLine());

		for (int i = 0; i < n; i++) {
			liquid[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(liquid);
		// System.out.println(Arrays.toString(liquid));
		start = 0;
		end = n - 1;
		while (start != end) {
			int com = liquid[start] + liquid[end];
			// 만약 특성값이 더 작다면 갱신
			if (Math.abs(max) >= Math.abs(com)) {
				max = com;
				answer[0] = liquid[start];
				answer[1] = liquid[end];
			}
			// 여기서 특성값을 더 줄일 수 있게 포인터를 조정해야 함.
			// start를 움직이느냐, end를 움직이느냐 -> 절대값이 더 큰 녀석을 움직이자
			if (Math.abs(liquid[start]) > Math.abs(liquid[end])) {
				start += 1;
			} else {
				end -= 1;
			}
		}
		System.out.println(answer[0] + " " + answer[1]);
	}

}

---