[BOJ] 2470번 두 용액 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {

    static int N;
    static int[] arr, result;

    public static void main(String[] args) throws IOException {
        init();
        process();
        printResult();
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        result = new int[2];	// 최소가 되는 결과를 담기 위한 배열
        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);
    }

    private static void process() {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            int start = i + 1;
            int end = N-1;
            min = binarySearch(min, i, start, end);
        }
    }

    private static int binarySearch(int min, int i, int start, int end) {
        while (start <= end) {
            int mid = (start + end) / 2;
            int sum = arr[i] + arr[mid];
            int diff = Math.abs(sum);	// 0과의 차이 : 절댓값
            if (diff < min) {
                min = diff;
                result[0] = arr[i];
                result[1] = arr[mid];
            }
			// 두 수의 합이 음수인 경우 왼쪽 탐색
            if (sum < 0) {
                start = mid + 1;
            } 
            // 두 수의 합이 0 이상인 경우 오른쪽 탐색
            else {
                end = mid - 1;
            }
        }
        return min;
    }

    private static void printResult() {
        for (int i : result) {
            System.out.print(i + " ");
        }
    }
}

📄 해설

• 이진탐색 활용 문제. 굉장히 어려웠음
• 두 수의 비교가 필요하므로, 0부터 N까지 반복을 수행해야함
• i 번째 수와 i+1 ~ N 까지의 범위에서 수를 하나 뽑아서 더했을 때, 0에 가장 가까운 경우를 찾으면 됨
• i+1 ~ N 까지의 범위에서 수를 뽑는 방법에 이진 탐색을 적용하면 됨
• 이진탐색 과정(최솟값 갱신) -> binarySearch 메소드
  1. mid 값과 i 의 값의 합sum을 구함
  2. sum 의 절댓값인 diff 와 현재의 최솟값을 비교하여 최솟값을 갱신
  3. sum 이 0보다 작으면 왼쪽을 탐색하고, 0보다 크거나 같으면 오른쪽을 탐색

후기

• 두번째 풀어보는 문제인데, 두 번 다 못푼 문제
• 이전에는 따로 정리하지 않고 넘어가기도 했고, 알고리즘 공부를 시작한지 얼마 안돼서 이번에 제대로 풀지 못한 것 같다
• 이제 정리했으니 다음엔 풀 수 있을...