백준 2473번 세 용액 - Java 이분탐색

 

노답 세 용액이다..!

 

오늘은 해장 알고리즘..

비전공자와 함께 토크토크하며 시작합니다..

 

 

문제를 정리하면 배열이 주어지고, 해당 배열에서 3가지를 선택해서 0에 가장 가깝게 만드는게 관건이다.

입력은 3 <= N <= 5000 이고, 숫자는 -10억 ~ 10억 까지로 주어진다.

 

🔹 인풋은 5,000 숫자 세개를 모두 탐색하게되면 N³. = 125,000,000,000 이 된다.

시간 제한 1초, 10⁸ 안팎이어야 하므로 이분탐색을 활용해서 시간을 log 대로 줄여보자.

 

해결 프로세스

1. 숫자를 정렬하자.

2. 두개를 먼저 이중 포문으로 고정하자.

3. 나머지 숫자는 고정된 값 + 탐색하는 값으로 0과 가까운지 확인하며 이분탐색으로 찾자.

4. 저장된 용액보다 0과 가깝다면 업데이트 해자.

5. 0을 만들거나, 모든 경우의 수를 따졌다면 최적의 결과를 출력하자.

 

정렬에 N log N, 이중 포문 N², 이진 탐색 log N = O(N² * log N)  으로 줄일 수 있다.

N ²  × log N ≈ 25,000,000 × 12.3 ≈ 307,500,000 이므로 1초 안팎으로 가능하다.

작성해보자

 

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));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
 
        long[] arr = new long[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        Arrays.sort(arr);
        long best = Long.MAX_VALUE;
        long[] result = new long[3];
 
        // 숫자 두개 고정.
        for (int i = 0; i < N - 2; i++) {
            for (int j = i + 1; j < N - 1; j++) {
                long now= arr[i];
                long next = arr[j];
                int min = j + 1;
                int max = N - 1;
                int mid = 0;
 
                long sum = 0;
                while (min <= max) {
                    mid = (min + max) / 2;
                    sum = now + next + arr[mid];
                    
                    // 이전 기록보다 좋은 용액이라면 업데이트
                    if (Math.abs(sum) < Math.abs(best)) {
                        best = sum;
                        result[0] = now;
                        result[1] = next;
                        result[2] = arr[mid];
                    }
 
                    if (sum > 0) {
                        max = mid - 1;
                    } else if (sum < 0) {
                        min = mid + 1;
                    } else {
                        // 0 을 만든 
                        System.out.println(now + " " + next + " " + arr[mid]);
                        return;
                    }
                }
            }
        }
        System.out.println(result[0] + " " + result[1] + " " + result[2]);
    }
}