링크

2467 용액

문제

풀이

시간 되게 많이 썼다. 바보 같이 스페셜저지인데 그걸 생각못하고 output이 계속 달라서 계속 풀었다 ㅋㅋ...
두 용액과 같은 문제이지만 두 용액은 투포인터로 해결했고 용액은 이분탐색을 통해 해결했다.

현재 선택한 요소를 element라고 가정하고
이분탐색을 통해 찾은 요소를 mid라고 가정한다면
이분탐색을 통해 Math.abs(element + mid)가 0에 가장 가까운 값을 구하면 된다.

그리고 이 문제는 보통 이분탐색보다 더 복잡하게 for문을 통해 각 element에 대하여(인덱스 0부터 n-1까지) 이분탐색을 통해 element와 어떤 값을 더해야 0에 가장 가까운지를 찾아내야 한다.

내가 푼 풀이

(복잡하지만 대충 이런식으로 풀었다.)
먼약 -99 -2 -1 5 98이 있다고 하면 -99랑 나머지 값들 중 하나를 더해서 이분탐색을 통해 0에 가장 가깝게 만들어야 한다.
start값은 -2, end값은 98로 잡고 가장 -99와 어떤 값을 더했을때 가장 작은 값을 갱신해나가면 된다.

코드

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


public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];

        for(int i=0;i<arr.length;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // System.out.println(Arrays.toString(arr));
        Arrays.sort(arr);

        // 현재 요소들을 골라서 이진탐색을 통해 요소*-1과 가까운 값을 찾는다.
        int ansLeft = -1;
        int ansRight = -1;

        //두개 더했을때 합
        long minSum = Long.MAX_VALUE;

        for(int i=0;i<arr.length;i++){
            int start = i+1;
            int end = n-1;

            while(start <= end){
                int mid = (start + end) / 2;
                long sum = Math.abs(arr[i] + arr[mid]);
//                System.out.println("start = " + start + ", end = " + end + ", mid = " + mid);

                if(minSum > sum){
//                    System.out.println("ansLeft = " + ansLeft + ", ansRight = " + ansRight);
//                    System.out.println("mid = " + mid + ", arr[mid] = " + arr[mid]);
//                    System.out.println("minSUm = " + minSum + ", sum = " + sum);
                    minSum = sum;
                    ansLeft = i;
                    ansRight = mid;
//                    System.out.println("");
                }

                if(arr[i] + arr[mid] <= 0){
                    start = mid + 1;
                } else{
                    end = mid - 1;
                }

            }


        }

        System.out.println(arr[ansLeft] + " " + arr[ansRight]);
    }

}