문제 링크
1. 문제 풀이
주어진 정수 값의 용액들에 대해 두 용액의 합이 $0$ 에 최대한 가까운 조합을 찾아서 출력해야 하는 문제다. $N$ 이 최대 $100,000$ 이라서 2중 반복문을 활용한 브루트 포스로는 해결할 수 없는데, 이분 탐색 또는 투 포인터 알고리즘을 활용하면 해결할 수 있다.
1. 이분 탐색
이분 탐색을 활용할 경우 특정 용액에 대해 합했을 때 $0$ 에 최대한 가까운 용액을 찾아야 한다. 이를 위해 Lower Bound, Upper Bound 이분 탐색을 활용했고 합했을 때 $0$ 에 가까워지려면 특정 용액의 부호를 바꿔서 탐색을 하면 된다. 이렇게 부호를 반전했을 때 해당 값 이상인 용액 중 가장 작은 용액과 해당 값 이하인 용액 중 가장 큰 용액을 후보로 찾았다.
이후 각 후보 용액이 실제로 존재하며(Lower Bound, Upper Bound는 인덱스 바깥 값도 반환할 수 있음) 자기 자신이 아닐 경우 두 용액의 합이 현재까지 구한 가장 작은 조합보다 작은지 비교해서 갱신하도록 구현했다.
이분 탐색 범위의 경우 특정 용액의 오른쪽 용액들에 대해서만 탐색하면 되는데 왼쪽 용액들의 경우 이미 특정 용액 이전에 해당 조합을 찾았을 것이기 때문에 중복 탐색이 된다.
2. 투 포인터
투 포인터를 활용할 경우 두 개의 포인터를 각각 주어진 용액 배열의 양 끝에 위치시키고 서로 엇갈리기 전까지 탐색하면 된다. 탐색 조건은 두 포인터에 해당하는 용액의 합이 $0$ 보다 크면 오른쪽 포인터를 이동시켜 합이 작아지게 하고, $0$ 보다 작으면 왼쪽 포인터를 이동시켜 합이 커지게 하면 된다. 각 과정에서 매번 두 용액의 합이 현재까지 찾은 조합보다 더 작은지 계산도 수행했다.
2. 코드
1. 이분 탐색 [Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
int sum = Integer.MAX_VALUE;
int[] ans = {0, 0};
for (int i = 0; i < N - 1; i++) {
int idx1 = lowerBound(arr, i + 1, -arr[i]);
int idx2 = upperBound(arr, i + 1, -arr[i]) - 1;
if (idx1 != N && Math.abs(arr[i] + arr[idx1]) < sum) {
sum = Math.abs(arr[i] + arr[idx1]);
ans[0] = arr[i];
ans[1] = arr[idx1];
}
if (idx2 != i && idx2 != N && Math.abs(arr[i] + arr[idx2]) < sum) {
sum = Math.abs(arr[i] + arr[idx2]);
ans[0] = arr[i];
ans[1] = arr[idx2];
}
}
System.out.printf("%d %d", ans[0], ans[1]);
}
static int lowerBound(int[] arr, int left, int key) {
int right = arr.length;
while (left < right) {
int mid = (left + right) / 2;
if (arr[mid] < key) {
left = mid + 1;
} else {
right = mid;
}
}
return right;
}
static int upperBound(int[] arr, int left, int key) {
int right = arr.length;
while (left < right) {
int mid = (left + right) / 2;
if (arr[mid] <= key) {
left = mid + 1;
} else {
right = mid;
}
}
return right;
}
}
|
2. 투 포인터 [Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N];
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;
int sum = Integer.MAX_VALUE;
int[] ans = {0, 0};
while (left < right) {
if (arr[left] + arr[right] > 0) {
if (Math.abs(arr[left] + arr[right]) < sum) {
sum = Math.abs(arr[left] + arr[right]);
ans[0] = arr[left];
ans[1] = arr[right];
}
right--;
} else if (arr[left] + arr[right] < 0) {
if (Math.abs(arr[left] + arr[right]) < sum) {
sum = Math.abs(arr[left] + arr[right]);
ans[0] = arr[left];
ans[1] = arr[right];
}
left++;
} else {
ans[0] = arr[left];
ans[1] = arr[right];
break;
}
}
System.out.printf("%d %d", ans[0], ans[1]);
}
}
|
3. 이분 탐색 [C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> v(n);
for (int& x : v) cin >> x;
sort(v.begin(), v.end());
int sum = INT_MAX;
pair<int, int> ans{};
for (int i = 0; i < n - 1; i++) {
int idx1 = lower_bound(v.begin() + i + 1, v.end(), -v[i]) - v.begin();
int idx2 = upper_bound(v.begin() + i + 1, v.end(), -v[i]) - v.begin() - 1;
if (idx1 != n && abs(v[i] + v[idx1]) < sum) {
sum = abs(v[i] + v[idx1]);
ans = {v[i], v[idx1]};
}
if (idx2 != i && idx2 != n && abs(v[i] + v[idx2]) < sum) {
sum = abs(v[i] + v[idx2]);
ans = {v[i], v[idx2]};
}
}
cout << ans.first << ' ' << ans.second;
}
|
4. 투 포인터 [C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> v(n);
for (int& x : v) cin >> x;
sort(v.begin(), v.end());
int l = 0;
int r = n - 1;
int sum = INT_MAX;
pair<int, int> ans{};
while (l < r) {
if (v[l] + v[r] > 0) {
if (abs(v[l] + v[r]) < sum) {
sum = abs(v[l] + v[r]);
ans = {v[l], v[r]};
}
r--;
} else if (v[l] + v[r] < 0) {
if (abs(v[l] + v[r]) < sum) {
sum = abs(v[l] + v[r]);
ans = {v[l], v[r]};
}
l++;
} else {
ans = {v[l], v[r]};
break;
}
}
cout << ans.first << ' ' << ans.second;
}
|
3. 풀이 정보
1. 이분 탐색 [Java]
| 언어 | 시간 | 메모리 | 코드 길이 |
|---|
| Java 11 | 364 ms | 28428 KB | 1880 B |
2. 투 포인터 [Java]
| 언어 | 시간 | 메모리 | 코드 길이 |
|---|
| Java 11 | 328 ms | 28260 KB | 1433 B |
3. 이분 탐색 [C++]
| 언어 | 시간 | 메모리 | 코드 길이 |
|---|
| C++ 17 | 20 ms | 2412 KB | 820 B |
4. 투 포인터 [C++]
| 언어 | 시간 | 메모리 | 코드 길이 |
|---|
| C++ 17 | 12 ms | 2412 KB | 828 B |