백준 2467_용액_JAVA

 

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

 

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));

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];

        int firstAnswer = 0;
        int secondAnswer = 0;
        int value = Integer.MAX_VALUE; // 두 수의 합이 0에 가장 가까운지 확인하기 위해

        StringTokenizer st = new StringTokenizer(br.readLine());

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

        for (int i = 0; i < n; i++) { // 하나 하나 확인하기 위해
            int min = i + 1; // 가장 작은 수가 있는 인덱스
            int max = n - 1; // 가장 큰 수가 있는 인덱스

            while (min <= max) {
                int mid = (min + max) / 2;

                int sum = arr[i] + arr[mid]; 

                if (value > Math.abs(sum)) { // 0에 가장 가까운 두 수인지 확인 후 저장
                    firstAnswer = arr[i];
                    secondAnswer = arr[mid];
                    value = Math.abs(sum);
                }

                if (sum < 0) { 
                    min = mid + 1;
                } else {
                    max = mid - 1;
                }

            }
        }

        System.out.print(firstAnswer);
        System.out.print(" ");
        System.out.print(secondAnswer);
    }
}

 

 

회고

- 이분탐색은 구현은 정말 간단하고 쉬운데 떠올리기가 굉장히 어려운 것 같다.

- 많이 풀어봐야겠다

- 그래도 골드4 치고 다른 알고리즘들 보단 쉬운 것 같다