[백준] 2467. 용액

https://www.acmicpc.net/problem/2467

2467번: 용액

이 문제는 이분탐색으로도 풀 수 있고, 투포인터로도 풀 수 있다.

이분탐색

• 수를 두개씩 더해서 그 절댓값이 가장 작은 것이 답이 된다.
• 이때 이중 반복문으로 수를 더하면 O(N^2)의 시간 복잡도가 발생한다. 따라서 이분탐색으로 풀어야 한다. (시간 복잡도: O(N * logN))
• 배열을 정렬한 후 특정 인덱스를 기준으로, 해당 인덱스보다 큰 인덱스들을 범위로 이분탐색하여, 더한 값의 절댓값이 가장 작은 수를 계속 갱신해나가면 된다.
• 이때 주의할 점은 특정 인덱스를 기준으로 할 때, 해당 인덱스보다 작거나 같은 인덱스는 탐색할 필요없다. 예를 들어 -99, 98이나 98, -99나 같기 때문에 중복을 제거하는 것이다.
• 그리고 두 수의 합이 0보다 크면 왼쪽 범위로 탐색 범위를 옮기고, 두 수의 합이 0보다 작으면 오른쪽 범위로 탐색 범위를 옮기면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

// 시간 복잡도: O(N * logN)
public class Main {

    static int n;
    static int[] arr;
    static long answer = Long.MAX_VALUE;
    static int[] answerNumberArr = new int[2];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        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);

        for (int i = 0; i < n - 1; i++) {
            int minIdx = i + 1;
            int maxIdx = n - 1;

            while (minIdx <= maxIdx) {
                int midIdx = (minIdx + maxIdx) / 2;
                long sum = arr[i] + arr[midIdx];

                if (answer > Math.abs(sum)) {
                    answer = Math.abs(sum);
                    answerNumberArr[0] = arr[i];
                    answerNumberArr[1] = arr[midIdx];
                }

                if (sum <= 0) {
                    minIdx = midIdx + 1;
                } else {
                    maxIdx = midIdx - 1;
                }
            }
        }

        for (int i : answerNumberArr) {
            System.out.print(i + " ");
        }
    }
}

투포인터

• 투포인터로 풀면 O(N) 시간만에 풀 수 있다.
• 이분탐색에서의 아이디어와 같다.
• 우선 시작 점인 left를 0으로, 끝 점임 right를 n-1로 둔다.
• 그리고 시작 점과 끝 점 사이 값의 합을 구해서, 합의 절댓값이 작으면 갱신한다.
• 그리고 합이 0보다 크거나 같으면 끝 점을 한 칸 왼쪽으로 옮기고, 합이 0보다 작으면 시작 점을 한 칸 오른쪽으로 옮긴다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

// 시간 복잡도: O(N)
public class Main {

    static int n;
    static int[] arr;
    static long answer = Long.MAX_VALUE;
    static int[] answerNumberArr = new int[2];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        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);

        int left = 0;
        int right = n - 1;
        while (left < right) {
            int sum = arr[left] + arr[right];
            if (answer > Math.abs(sum)) {
                answer = Math.abs(sum);
                answerNumberArr[0] = arr[left];
                answerNumberArr[1] = arr[right];
            }

            if (sum >= 0) {
                right--;
            } else {
                left++;
            }
        }

        for (int i : answerNumberArr) {
            System.out.print(i + " ");
        }
    }
}