[ baekjoon ] 두 용액 2470번 ( Java )

문제

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

2470번: 두 용액

 

풀이

이진 탐색을 이용해서 풀었다. 일단 이진 탐색을 해야 하기에 먼저 정렬을 진행했고,

풀이는 첫 번째 테스트 케이스를 예를 들어서

-99 -2 -1 4 98

위의 값들이 들어오게 되는데, 첫 번째 -99에 더해서 0이 되는 값은 99이다.

그러므로 -99 다음 값들중 99에 가장 가까운 값들을 찾으면 되는 방법으로 했는데, 값을 찾을 때 이진 탐색을 이용했다.

이 값들 중 0에 가장 가까운 값들을 찾는다.

package baekjoon;

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

public class _2470 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[] 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 answer = Integer.MAX_VALUE;
        int ans1 = 0;
        int ans2 = 0;

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

            int now = arr[i];
            int target = now * -1;

            int tmp = binary_search(i + 1, n, target, arr, n);

            int sum = Math.abs(arr[i] + tmp);
            if (Math.abs(answer) >= sum) {
                answer = sum;
                ans1 = arr[i];
                ans2 = tmp;
            }
        }

        if (ans1 < ans2) {
            System.out.println(ans1 + " " + ans2);
        } else {
            System.out.println(ans2 + " " + ans1);
        }


    }

    public static int binary_search(int start, int end, int target, int[] arr, int n) {
        int min  = Integer.MAX_VALUE;
        int answer = 0;

        while (start < end) {
            int mid = (start + end) / 2;

            if (Math.abs(target - arr[mid]) < min) {
                min = Math.abs(target - arr[mid]);
                answer = arr[mid];
            }
            if (arr[mid] < target) {
                start = mid + 1;
            } else if (arr[mid] > target) {
                end = mid;
            } else {
                return target;
            }
        }

        return answer;
    }
}