백준 두 용액(2470)

두 용액

1. 힌트

1) 주어진 수열을 정렬해볼 수 있습니다.

2) 임의의 두 용액을 $p,\ q$라고 했을 때, 탐색 순서를 잘 조정하면 모든 $p, q$쌍을 확인하지 않고도 답을 알 수 있습니다.

3) 투 포인터 알고리즘을 사용해서 양 끝에서부터 포인터를 줄여나가면 답이 될 수 있는 모든 $p,\ q$쌍만을 확인할 수 있습니다.

2. 접근

1) 순서를 강제할 수 있을까?

주어진 수열 $S$를 정렬하고, 답이 될 수 있는 두 용액의 위치 $(p,\ q)$를 모두 확인합니다. 중복을 방지하기 위해서 용액의 특성값은 $S[p]$가 $S[q]$보다 작게 고릅시다. 또, $(p,\ q)$를 탐색하는 순서는 문제의 답과 상관이 없으므로 특성값이 작은 용액부터 큰 용액 순으로 $p$를 고른다고 순서를 강제하겠습니다.
만약 $p$가 정해져 있다면 $p$와 합쳤을 때 특성값이 $0$에 가장 가까워지는 용액 $q$는 유일합니다(용액들의 특성값은 모두 다르므로). $|S[p]+S[q]|$를 $q$를 계속 왼쪽으로 이동시키다보면 어느 순간 이 값이 증가하게되는데 증가하기 전까지 계속해서 이동시키면 그 $(p,\ q)$쌍이 $0$에 가장 가까운 값입니다. 그리고 $p$를 한 칸 앞으로 전진시킬때, $q$를 다시 처음부터 찾을 필요 없이 그대로 유지시켜도 됨을 알 수 있습니다.

3. 구현

Arrays.sort()는 퀵 소트 기반이기 때문에 최악의 경우 $O(N^2)$의 시간이 걸릴 수 있습니다. 이 문제는 그러한 테스트 케이스가 없어서 사용할 수 있습니다. 안전하게 $O(NlgN)$이 보장되는 Collections.sort()사용을 추천드립니다.

import java.io.*;
import java.util.*;

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());
		int[] S = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) S[i] = Integer.parseInt(st.nextToken());
		Arrays.sort(S);
		int head = 0; int tail = N - 1;
		int abs = Math.abs(S[head] + S[tail]);
		// 최적해 min과 실제 답 p
		int min = abs; int[] p = new int[] { head, tail };
		// (head, tail)쌍은 순서가 상관 없으므로 증가하는 순서인 것만 확인한다
		while (head < tail) {
			// S[head]와 더했을 때 가장 0에 가까운 S[tail]까지 이동시킨다
			while (head < tail - 1 && Math.abs(S[head] + S[tail - 1]) < abs) {
				tail--;
				abs = Math.abs(S[head] + S[tail]);
			}
			if (min > abs) {
				min = abs;
				p[0] = head; p[1] = tail;
			}
			head++;
			abs = Math.abs(S[head] + S[tail]);
		}
		System.out.printf("%d %d\n", S[p[0]], S[p[1]]);
	}

}

1) 시간 복잡도

바깥쪽 while문은 최대 $O(N)$번 반복될 수 있고, 안쪽 while문도 마찬가지이므로 $O(N + N)$으로 $O(N)$입니다.

2) 테스트 케이스