https://www.acmicpc.net/problem/2470
사용 알고리즘
- 투 포인터
- 이분탐색
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int n;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
int [] arr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
// -99, -2, -1, 4, 98
// -100 1 2 100 10000
int lo = 0;
int hi = n - 1;
long min = Integer.MAX_VALUE;
int [] res = new int[2];
while(lo < hi) {
long sum = arr[lo] + arr[hi];
if (Math.min(min, Math.abs(sum)) == Math.abs(sum)) {
min = Math.abs(sum);
res[0] = arr[lo];
res[1] = arr[hi];
}
if (sum > 0) hi--;
else lo++;
}
System.out.println(res[0] + " " + res[1]);
}
}
회고
오전에 잠깐 풀 때는 안풀리다가 오후에 다시 시도하니 한번에 통과했다.
이분탐색 + 투포인터를 조합해서 풀었다. Array.sort로 O(nlogn), 투포인터로 O(n)이라 최종 시간복잡도는 O(nlogn)이고, n이 10만일 때도 1초안에 무사히 통과된다.
lo와 hi의 절댓값 합을 구한 다음에 작을 때 계속 갱신해주고, 합이 0보다 클 때는 상한점을 낮춰서 0에 가깝게 하고, 0보다 작을 때는 하한점을 높여 0과 가깝게 설정해서 풀이했다.
'Algorithm > 백준' 카테고리의 다른 글
[백준] Silver II. 생태학 (0) | 2024.07.22 |
---|---|
[백준] Gold IV. 부분 합 (0) | 2024.07.21 |
[백준] Gold V. 수 고르기 (0) | 2024.07.20 |
[백준] Gold IV. 합이 0 (0) | 2024.07.20 |
[백준] Gold V. 가장 긴 짝수 연속한 부분 수열 (large) (0) | 2024.07.19 |