[BOJ] 2467. 용액 (🥇, 이분탐색, 투포인터)

🔗

풀이

이분탐색

숫자 하나를 기준으로 삼고, 나머지 숫자들 가운데 기준으로 삼은 숫자와 더했을 때 가장 0에 가까울 수 있는 숫자가 무엇인지 찾는 방법을 생각했다. 주어지는 숫자는 10만개이고 오름차순 정렬로 주어진다. 10만개의 숫자에 대해 한번씩 기준 숫자로 정하고, 기준 숫자의 오른쪽에 있는 숫자부터 마지막까지 숫자들 가운데 합이 0에 가까운 숫자 조합을 찾으면 된다. 정렬되어있기 때문에 값을 찾는 과정은 이분탐색으로 수행했다.

문제에 주어지는 테스트케이스를 기준으로 하면 위와 같이 찾을 수 있다. -99, -2, -1, 4가 모두 한 번씩 기준 숫자가 될 수 있다. 해당 기준 숫자의 오른쪽에 대해서만 탐색을 진행하는데 왼쪽 범위의 숫자는 이미 해당 숫자들이 기준 숫자일 때 탐색을 끝냈을 것이기 때문에 굳이 두 번 진행할 필요는 없다. 마지막 숫자인 98은 해당 숫자의 오른쪽에 숫자가 없으므로 탐색을 진행하지 않는다.

처음에는 0에 가장 가까운 숫자를 마지막까지 찾아내는 방식으로 탐색을 진행했지만, 마지막에 탐색되는 숫자가 항상 0과 가장 가까운 합을 갖지는 않는다. 때문에 탐색 도중에 합이 0과 가까운 값이 나오게 되면 answer 배열의 값을 업데이트하고 탐색을 진행한다. 아래 테스트케이스에서 -2가 기준일 때 -1이 0과 가장 가까운 값을 갖게 되는데 이분 탐색을 끝까지 진행하기만 하면 103 에서 종료되기 때문에 오답이 된다. 하지만 도중에 값을 계속 업데이트하면 -1이 저장되고 종료된다 이 방식은 이분탐색이다.

4
-100 -2 -1 103

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N;
    static long[] values;
    static long[] binarySearch(long stdNum, int left) {
        int right = N-1;
        int mid = (left + right) / 2;
        long sum;
        long[] answer = new long[] {2_000_000_000, stdNum, values[N-1]};

        while (left <= right) {
            mid = (left + right) / 2;
            sum = stdNum + values[mid];
            if (Math.abs(sum) < answer[0]) {
                answer[0] = Math.abs(sum);
                answer[2] = values[mid];
            }

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

        return answer;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        values = new long[N];

        for (int i = 0; i < N; i++) {
            values[i] = sc.nextLong();
        }

        long[] answer = new long[] {2_000_000_000, 0, 0};
        long[] tmp;
        for (int i = 0; i < N-1; i++) {
            tmp = binarySearch(values[i], i+1);
            if (tmp[0] <= answer[0]) {
                answer = tmp;
            }
        }

        System.out.println(answer[1] + " " + answer[2]);

    }
}

투 포인터

오름차순 정렬 상태이므로 가장 왼쪽 값을 startIdx 가장 오른쪽 값을 endIdx 로 두고 두 인덱스가 가리키는 값의 합이 0에 가까운지 여부를 판단한다. 만약 현재 저장된 값보다 0에 더 가까운 값이라면 업데이트 한다.

startIdx를 증가시키면 더하는 값을 증가시키는 것이고, endIdx는 더하는 값을 감소시키는 것이다. 만약 두 값을 더한 합이 0보다 작다면 startIdx를 증가시키면 합이 0에 가까워질 확률이 높아지고, 0보다 크다면 endIdx를 감소시키면 합이 0에 가까워질 확률이 높아진다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static long[] values;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        values = new long[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            values[i] = Long.parseLong(st.nextToken());
        }

        long minValue = Long.MAX_VALUE;
        int startIdx = 0;
        int endIdx = N-1;
        long sum;
        int left = 0;
        int right = N-1;
        while (startIdx < endIdx) {
            sum = values[startIdx] + values[endIdx];
            if (Math.abs(sum) < minValue) {
                minValue = Math.abs(sum);
                left = startIdx;
                right = endIdx;
            }

            if (sum < 0) {
                startIdx++;
            } else {
                endIdx--;
            }
        }

        System.out.println(values[left] + " " + values[right]);

    }
}