[BaekJoon] 2473번 - 세 용액 [Java][C++]
[BaekJoon] 2473번 - 세 용액 [Java][C++]
1. 문제 풀이
BaekJoon 2467번 - 용액 문제에서 세 용액의 합으로 바뀐 문제로 이분 탐색으로 해결할 경우 두 개의 용액을 2중 반복문으로 선택한 후 남은 하나를 이분 탐색으로 찾으면 되며, 투 포인터로 해결할 경우 한 용액을 선택한 후 투 포인터로 남은 두 용액을 탐색하면 된다.
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
73
74
75
76
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);
long sum = 3_000_000_000L;
int[] ans = {0, 0, 0};
for (int i = 0; i < N - 2; i++) {
for (int j = i + 1; j < N - 1; j++) {
int idx1 = lowerBound(arr, j + 1, -(arr[i] + arr[j]));
int idx2 = upperBound(arr, j + 1, -(arr[i] + arr[j])) - 1;
if (idx1 != N && Math.abs((long) arr[i] + arr[j] + arr[idx1]) < sum) {
sum = Math.abs((long) arr[i] + arr[j] + arr[idx1]);
ans[0] = arr[i];
ans[1] = arr[j];
ans[2] = arr[idx1];
}
if (idx2 != j && idx2 != N && Math.abs((long) arr[i] + arr[j] + arr[idx2]) < sum) {
sum = Math.abs((long) arr[i] + arr[j] + arr[idx2]);
ans[0] = arr[i];
ans[1] = arr[j];
ans[2] = arr[idx2];
}
}
}
System.out.printf("%d %d %d", ans[0], ans[1], ans[2]);
}
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
48
49
50
51
52
53
54
55
56
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);
long sum = 3_000_000_000L;
int[] ans = {0, 0, 0};
out:
for (int i = 0; i < N - 2; i++) {
long num = arr[i];
int left = i + 1;
int right = N - 1;
while (left < right) {
if (num + arr[left] + arr[right] > 0) {
if (Math.abs(num + arr[left] + arr[right]) < sum) {
sum = Math.abs(num + arr[left] + arr[right]);
ans[0] = arr[i];
ans[1] = arr[left];
ans[2] = arr[right];
}
right--;
} else if (num + arr[left] + arr[right] < 0) {
if (Math.abs(num + arr[left] + arr[right]) < sum) {
sum = Math.abs(num + arr[left] + arr[right]);
ans[0] = arr[i];
ans[1] = arr[left];
ans[2] = arr[right];
}
left++;
} else {
ans[0] = arr[i];
ans[1] = arr[left];
ans[2] = arr[right];
break out;
}
}
}
System.out.printf("%d %d %d", ans[0], ans[1], ans[2]);
}
}
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
35
36
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> v(n);
for (long long& x : v) cin >> x;
sort(v.begin(), v.end());
long long sum = 3000000000LL;
vector<long long> ans(3);
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
int idx1 = lower_bound(v.begin() + j + 1, v.end(), -(v[i] + v[j])) - v.begin();
int idx2 = upper_bound(v.begin() + j + 1, v.end(), -(v[i] + v[j])) - v.begin() - 1;
if (idx1 != n && llabs(v[i] + v[j] + v[idx1]) < sum) {
sum = llabs(v[i] + v[j] + v[idx1]);
ans = {v[i], v[j], v[idx1]};
}
if (idx2 != j && idx2 != n && llabs(v[i] + v[j] + v[idx2]) < sum) {
sum = llabs(v[i] + v[j] + v[idx2]);
ans = {v[i], v[j], v[idx2]};
}
}
}
cout << ans[0] << ' ' << ans[1] << ' ' << ans[2];
}
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
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> v(n);
for (long long& x : v) cin >> x;
sort(v.begin(), v.end());
long long sum = 3000000000LL;
vector<long long> ans(3);
for (int i = 0; i < n - 2; i++) {
long long num = v[i];
int l = i + 1;
int r = n - 1;
while (l < r) {
if (num + v[l] + v[r] > 0) {
if (llabs(num + v[l] + v[r]) < sum) {
sum = llabs(num + v[l] + v[r]);
ans = {v[i], v[l], v[r]};
}
r--;
} else if (num + v[l] + v[r] < 0) {
if (llabs(num + v[l] + v[r]) < sum) {
sum = llabs(num + v[l] + v[r]);
ans = {v[i], v[l], v[r]};
}
l++;
} else {
ans = {v[i], v[l], v[r]};
cout << ans[0] << ' ' << ans[1] << ' ' << ans[2];
return 0;
}
}
}
cout << ans[0] << ' ' << ans[1] << ' ' << ans[2];
}
This post is licensed under CC BY 4.0 by the author.