❓문제 설명
문제 링크 : https://www.acmicpc.net/problem/2473
N개의 용액 중 서로 다른 세 용액을 골라 혼합했을 때, 특성값의 합이 0에 가장 가까운 조합을 찾기
용액의 특성값은 -1,000,000,000 이상 1,000,000,000 이하의 정수 및 양수 또는 음수이다.
KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.
같은 양의 세 가지 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 세 가지 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.
예를 들어, 주어진 용액들의 특성값이 [-2, 6, -97, -6, 98]인 경우에는 특성값이 -97와 -2인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 세 종류의 알칼리성 용액만으로나 혹은 세 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.
산성 용액과 알칼리성 용액이 주어졌을 때, 이 중 같은 양의 세 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 세 용액을 찾는 프로그램을 작성하시오.
❗입출력
입력
- 첫째 줄: 용액의 수 N (3 ≤ N ≤ 5,000)
- 둘째 줄: N개의 용액 특성값 (공백 구분, 모두 다름)
출력
- 특성값의 합이 0에 가장 가까운 세 용액의 특성값을 오름차순으로 출력
- 여러 조합이 있을 경우, 그 중 아무거나 출력 가능
🎁 문제 풀이
고정값을 하나 두고, 투포인터를 활용한다.
투포인터를 쓴다면 단순하지만, 고정값이 있다는 부분에서 포인터 이동 조건이 헷갈렸다.
결과적으로 한번 확인한 값은 다시 확인할 필요가 없으므로,
고정값 이후로 포인터를 지정하고, left < right 의 조건 안에서 포인터를 이동한다.
용액의 합이 양수라면 양수 방향의 값(right)를 작게 이동한다.
합이 음수라면 음수 방향의 값(left)을 크게 이동한다.
🖥️ 코드
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());
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
long[] arr = new long[N];
for(int i = 0; i < N; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
long[] answer = solution(arr);
Arrays.sort(answer);
for(long l : answer) {
System.out.print(l + " ");
}
}
private static long[] solution(long[] arr) {
int N = arr.length;
long min = Long.MAX_VALUE;
long[] answer = new long[3];
for(int i = 0; i < N-2; i++) {
int left = i + 1;
int right = N - 1;
while (left < right) {
long sum = arr[i] + arr[left] + arr[right];
if(Math.abs(sum) < min) {
min = Math.abs(sum);
answer[0] = arr[i];
answer[1] = arr[left];
answer[2] = arr[right];
}
if(sum > 0) {
right--;
} else if (sum < 0) {
left++;
} else {
// sum == 0
return new long[] {arr[i], arr[left], arr[right]};
}
}
}
return answer;
}
}
작성자 : 연이현
