알고리즘
[Java] 백준 2473번 세 용액
J3SUNG
2023. 8. 1. 01:24
728x90
투포인터 문제입니다.
세개의 숫자를 골라서 합의 절대값이 0과 가장 가까운 값들을 찾아야합니다.
두개의 숫자를 고르는 (용액, 두 용액) 문제와 유사합니다.
N이 5000이므로 O(N^2)으로 처리할 수 있습니다.
0~N까지 고정점을 두고 나머지 두개의 수를 투포인터로 이동하면서 0과 가까운 수를 찾아주었습니다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
long goodSum = Long.MAX_VALUE;
int goodI = 0;
int goodLeft = 0;
int goodRight = 0;
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; ++i) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
for (int i = 0; i < n - 2; ++i) {
int left = i + 1;
int right = n - 1;
while (left < right) {
long sum = arr[left] + arr[right];
long sum2 = Math.abs(arr[i] + sum);
if (goodSum > sum2) {
goodSum = sum2;
goodI = i;
goodLeft = left;
goodRight = right;
}
if (arr[i] + sum > 0) {
--right;
} else {
++left;
}
}
}
bw.write(arr[goodI] + " " + arr[goodLeft] + " " + arr[goodRight] + "\n");
bw.close();
}
}