BOJ 2470 - 두 용액

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

 

 

서로 다른 두 용액을 더해서 합이 최대한 0에 가깝게 만드는 문제

 

아이디어

각 용액의 범위가 -10억 ~ 10억 이므로 두 용액을 합친 값의 범위는 -20억 ~ 20억이므로 int형 변수로 처리 가능하다. 

 

가장 먼저 생각난 방법은 이중 for문으로 두 용액을 섞을 수 있는 모든 경우를 다 비교해보는 것이다. 이렇게 하면 시간 복잡도가 O(N^2)이 된다. 이러면 N의 최댓값이 10억이니까 100억이 되버리므로 시간이 초과된다.

 

왼쪽 용액(left)을 골랐을 때 오른쪽 용액을 뭘 골라야 더해서 0에 가장 가까울까를 생각해보면 정렬이 된 용액들 중 A[left]를 고른 후 A[left+1 ~ N] 범위 내에서 -A[left]와 가장 가까운 수를 찾아 더해주면 0에 가장 가까울 것이다.

 

1. -A[left] 이상의 원소 중 가장 왼쪽 위치인 result를 얻는다.

    private static int low_bound(int[] A, int L, int R, int X) {
        // A[L...R]에서 X 이상의 수 중 제일 왼쪽 인덱스 return
        // 없다면 R+1 return
        int result = R + 1;
        while (L <= R) {
            int mid = (L + R) / 2;
            if (A[mid] >= X) {
                result = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }

        return result;
    }

 

2. A[result]와 A[result-1] 값 중 하나가 -A[left]와 가장 가까운 원소이므로 이 둘을 비교해서 답을 구한다.

			// CASE 1 : A[result -1]
            // 먼저 result -1 이 범위 안의 용액인지 확인
            if (left + 1 <= result - 1 && result - 1 <= N) {
                // 더한 후 절댓값과 best_sum을 비교 후 갱신
                if (Math.abs(A[result - 1] + A[left]) < best_sum) {
                    best_sum = Math.abs(A[left] + A[result - 1]);
                    v1 = A[left];
                    v2 = A[result - 1];
                }
            }

            // CASE 2 : A[result]
            // 먼저 result이 범위 안의 용액인지 확인
            if (left + 1 <= result && result <= N) {
                // 더한 후 절댓값과 best_sum을 비교 후 갱신
                if (Math.abs(A[result] + A[left]) < best_sum) {
                    best_sum = Math.abs(A[left] + A[result]);
                    v1 = A[left];
                    v2 = A[result];
                }
            }

 

 

시간 복잡도

1. 정렬 O(N log N)

2. 이분 탐색 O(N log N)

 

총 O(N log N)으로 시간 안에 풀이가 가능하다.

 

 

 

구현

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static int[] A;

    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        A = new int[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
    }

    static void pro() throws IOException {
        // 정렬
        Arrays.sort(A, 1, N + 1);

        int best_sum = Integer.MAX_VALUE;
        int v1 = 0;
        int v2 = 0;

        for (int left = 1; left <= N; left++) {
            // A[left] 용액 선택
            // (left+1 ~ N) 구간에서 -A[left]와 가장 가까운 용액 찾기
            int result = low_bound(A, left + 1, N, -A[left]);

            // A[result]와 A[result-1] 중 A[left]와 섞었을 때 0에 가까운 값 갱신

            // CASE 1 : A[result -1]
            // 먼저 result -1 이 범위 안의 용액인지 확인
            if (left + 1 <= result - 1 && result - 1 <= N) {
                // 더한 후 절댓값과 best_sum을 비교 후 갱신
                if (Math.abs(A[result - 1] + A[left]) < best_sum) {
                    best_sum = Math.abs(A[left] + A[result - 1]);
                    v1 = A[left];
                    v2 = A[result - 1];
                }
            }

            // CASE 2 : A[result]
            // 먼저 result이 범위 안의 용액인지 확인
            if (left + 1 <= result && result <= N) {
                // 더한 후 절댓값과 best_sum을 비교 후 갱신
                if (Math.abs(A[result] + A[left]) < best_sum) {
                    best_sum = Math.abs(A[left] + A[result]);
                    v1 = A[left];
                    v2 = A[result];
                }
            }
        }

        bw.write(v1 + " " + v2);
    }

    private static int low_bound(int[] A, int L, int R, int X) {
        // A[L...R]에서 X 이상의 수 중 제일 왼쪽 인덱스 return
        // 없다면 R+1 return
        int result = R + 1;
        while (L <= R) {
            int mid = (L + R) / 2;
            if (A[mid] >= X) {
                result = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }

        return result;
    }

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

        pro();

        bw.close();
    }

}