알고리즘
[Java] 백준 2470번 두 용액
J3SUNG
2023. 7. 27. 01:39
728x90
투포인터 문제입니다.
두개의 용액을 합쳐서 0과 가장 가까운수를 구해야합니다.
정렬을 한 다음 가장 왼쪽과 가장 오른쪽에 각각 포인터를 두고
두개의 합이 0보다 클 경우 오른쪽을 한칸 왼쪽으로 이동
두개의 합이 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];
int goodSum = 2_000_000_001;
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);
int left = 0;
int right = n - 1;
while (left < right) {
int sum = Math.abs(arr[left] + arr[right]);
if (goodSum > sum) {
goodSum = sum;
goodLeft = left;
goodRight = right;
}
if (arr[left] + arr[right] > 0) {
--right;
} else {
++left;
}
}
bw.write(arr[goodLeft] + " " + arr[goodRight] + "\n");
bw.close();
}
}