백준 2473번 : 세 용액 [Java]
https://www.acmicpc.net/problem/2473
문제 탐색하기
- 10억 ~ 10억 사이의 용액의 특성 값이 주어질 때 세 용액의 합이 0에 제일 가까울 경우를 출력하도록 하는 문제이다. N의 최소는 3 ~ 5000 사이의 수 일 때 위 세 용액을 어떻게 섞어야 할까?
시간 복잡도와 풀이를 생각해보기 전에 먼저 다양한 입력을 고려해봤다.
- 용액이 단 3개만 주어질 때
- 알칼리 용액만 주어질 때 (입력에 음수만 존재할 때)
- 산성 용액만 주어질 때 (입력에 양수만 존재할 때)
- 알칼리, 산성 용액이 모두 주어질 때
1번의 경우 정렬 후 출력만 하면 된다. 2, 3번의 경우도 마찬가지로 정렬 후 절댓값이 0과 가까운 세 수를 출력하면 된다. 여기서 해결해야 할 문제는 4번의 경우이다.
여러 예제를 통해 아래와 같은 풀이 방법들을 고려해봤다.
1. 정렬 후 0과 최대한 가까운 수 뽑기
다음과 같은 입력에서 정렬 후 0과 최대한 가까운 수를 하나 뽑고 low를 0, high를 n - 1 로 하여서 이분 탐색을 하는 계획을 생각해보았다.
5
-2 6 -97 -6 98
하지만 위의 경우 일단 어떤 조건으로 이분 탐색을 해야하는지? 절댓값이 같은 수가 있으면 어떤지? 등의 경우에서 옳지 못한 방법이란 걸 깨닫고 아래와 같은 반례가 금방 떠올랐다.
5
-98 -2 -1 84 100
2. 두 개를 뽑아서 더한 것들을 정렬하여 0과 최대한 가까운 수 뽑기
1번의 방법을 고도화해보려고 한 방법이다. 숫자 두 개를 미리 뽑아서 더하고 해당 숫자 정렬하여 0과 가까운 수를 몇개 뽑아 내는 방법이다. 이런 경우에서 생기는 문제는, 원래의 숫자를 찾기 위해 더 많은 메모리 공간을 소비하게 되고, 두개를 뽑은것에 한개를 다시 더해야 하는데 이럴 경우 시간 복잡도가 O(N^2 * log(N))이 되므로 시간 초과를 받을 것 같았다.
3. 그러면 그냥 완전 탐색을 하자.. 근데 이제 이분 탐색을 곁들인..
이런 경우에서는 그냥 모든 수를 정렬 후 1번 부터 n - 2 까지 이분탐색을 통해서 더 하면 된다. 1번 부터 n - 2번까지인 이유는 세 수를 뽑아야 하기 때문에 0번 과 n - 1 번째 수는 무조건 있어야 하기 때문이다. 이 때 범위 판별을 통해서 새로운 합의 절댓값이 0에 보다 근접하면 (기존 합의 절댓값 보다 작으면) 교체하고 세 수를 기록하는 방식으로 구현하면 된다.
low와 high는 각각 현재 합의 값이 0보다 작으면 음수 쪽에서 0에 근접하기 위해 low + 1을 하고 반대로 0보다 크면 양수 쪽에서 high - 1을 통해서 조절한다.
위 방식의 시간 복잡도는 전체를 탐색하는 값 * 이분탐색 비용이므로 O(Nlog(N))이 걸린다.
코드 설계하기
- 입력을 처리한 후 리스트에 담아서 이분 탐색을 위한 오름차순 처리를 한다
- 위에서 말한 1, 2, 3번에 해당하는 조건을 각각 처리한 후 출력한다.
- 모든 수를 탐색하면서 현재 합의 절댓값이 0에 근접한 수들을 기록한다. 매번 이분 탐색을 통해서 합의 절댓값의 최소를 찾으면 된다.
- 기록한 것을 출력한다.
풀이
import java.io.*;
import java.util.*;
public class Main {
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
long nextLong() {
return Long.parseLong(next());
}
}
static final int INF = (int) 1e9;
public static void main(String[] args) {
FastReader fr = new FastReader();
long N = fr.nextLong();
ArrayList<Long> list = new ArrayList<>();
for (int i = 0; i < N; i++) {
list.add(fr.nextLong());
}
Collections.sort(list);
if (N == 3) {
System.out.println(list.get(0) + " " + list.get(1) + " " + list.get(2));
return;
}
int alkali = INF;
int acid = INF;
for (int i = 0; i < N; i++) {
if (list.get(i) < 0) {
alkali = i;
}
if (list.get(i) > 0) {
acid = i;
break;
}
}
if (alkali != INF && acid == INF) {
System.out.println(list.get(alkali - 2) + " " + list.get(alkali - 1) + " " + list.get(alkali));
} else if (alkali == INF && acid != INF) {
System.out.println(list.get(acid) + " " + list.get(acid + 1) + " " + list.get(acid + 2));
} else {
long[] result = new long[3];
long closestSum = Long.MAX_VALUE;
for (int i = 1; i < (int)N - 1; i++) {
int low = 0;
int high = (int)N - 1;
while (low < i && i < high) {
long curSum = list.get(i) + list.get(low) + list.get(high);
if (Math.abs(curSum) < Math.abs(closestSum)) {
closestSum = curSum;
result[0] = list.get(low);
result[1] = list.get(i);
result[2] = list.get(high);
}
if (curSum == 0) {
System.out.println(result[0] + " " + result[1] + " " + result[2]);
return;
} else if (curSum < 0) {
low += 1;
} else {
high -= 1;
}
}
}
System.out.println(result[0] + " " + result[1] + " " + result[2]);
}
}
}