[BaekJoon] 2470번 - 두 용액 [Java][C++]

문제 링크

---

1. 문제 풀이

BaekJoon 2467번 - 용액 문제에서 용액들이 오름차순으로 주어지지 않은 문제로 입력을 받은 후 정렬만 한번 해주면 된다.

---

2. 코드

1. 이분 탐색 [Java]

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]

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++]

#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++]

#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;
}

---