[BOJ 2473] 세 용액 (Java)

BOJ 2473 세 용액

난이도 : 골드 3

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

2473번: 세 용액

 

전략

생각할 수 있는 가장 간단한 방법은 세 용액의 모든 조합을 찾는 것이다.

3중 for문으로 세 용액의 조합을 만든다면 O(N^3)이다.

N의 범위는 [3, 5000] 이므로 N^3은 5^3 * 10억이다. 따라서 다른 방법을 찾아야 한다.

 

만약 두 개의 용액 조합을 찾는다면 나머지 하나의 용액은 모두 찾을 필요 없이 이진 탐색으로 결정할 수 있다.

이는 O(N^2*logN)이 된다. 물론 이진 탐색을 위해서 정렬하는 시간일 필요하므로 N^2 * logN + logN이지만 이는 무시할 수 있다.

 

N^2은 25,000,000, logN은 12.x 정도 나올 것이므로 시간제한 1초 안에 간신히 가능할 것으로 보인다.

 

시행착오

각 용액의 농도의 범위는 [-10억, 10억]이므로 세 용액을 더 했을 때의 합은 int 형을 벗어날 수 있다.

따라서 합을 저장할 때는 반드시 long으로 타입 변환해야 한다. 이것 때문에 채점 테스트 케이스에서 실패하였었다.

 

코드

package BOJ_2473;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N;
        List<Integer> waters = new ArrayList<>();

        N = Integer.parseInt(br.readLine());
        String[] inputs = br.readLine().split(" ");
        for (String input : inputs) {
            waters.add(Integer.parseInt(input));
        }

        waters.sort((w1, w2) -> w1 - w2);

        int[] result = new int[3];
        long sum = Long.MAX_VALUE;

        for (int i = 0; i < waters.size() - 1; i++) {
            for (int j = i + 1; j < waters.size(); j++) {
                int look = (waters.get(i) + waters.get(j)) * -1;
                int pick = binSearch(waters, look);

                long matchPick = matched(waters, sum, i, j, pick);
                if (matchPick != -1) {
                    sum = matchPick;
                    saveResult(result, i, j, pick);
                }

                if (pick == 0) continue;

                long matchPickSecond = matched(waters, sum, i, j, pick - 1);
                if (matchPickSecond != -1) {
                    sum = matchPickSecond;
                    saveResult(result, i, j, pick - 1);
                }
            }
        }

        for (int idx : result) {
            System.out.print(waters.get(idx) + " ");
        }
    }

    static void saveResult(int[] result, int i, int j, int pick) {
        result[0] = i;
        result[1] = j;
        result[2] = pick;
        Arrays.sort(result);
    }

    // Returns abs if the condition is satisfied, otherwise returns -1
    static long matched(List<Integer> list, long sum, int i, int j, int picked) {
        long abs = Math.abs((long) list.get(i) + list.get(j) + list.get(picked));
        if (i != j && picked != i && picked != j && abs < sum)
            return abs;
        return -1;
    }

    // Find the nearest number that is not less than 'num'
    static int binSearch(List<Integer> list, int num) {
        int low = 0, high = list.size() - 1, mid = 0;

        while (low < high) {
            mid = (low + high) / 2;
            int look = list.get(mid);

            if (look == num) {
                return mid;
            }
            else if (look > num) {
                high = mid - 1;
            }
            else {
                low = mid + 1;
            }

            mid = (low + high) / 2;
        }

        return mid;
    }
}

이진 탐색에서는 num보다 작지 않은 가장 가까운 값을 반환하도록 하였다.

그 이유는 일치하는 값일 없을 경우에는 반환값과 이웃한 값 하나를 더 비교해야 한다.

이 때 항상 (반환 위치 - 1)의 값을 비교에 사용하여 인덱스를 벗어나지 않도록 하였다. 

 

이중 for문으로 두 개의 용액을 선택한 뒤에 (두 용액의 농도 합) * -1을 정렬된 리스트에서 이분 탐색한다.

그러면 선택된 두 용액 기준으로 0에 가장 가깝게 하는 나머지 용액이 선택된다. (탐색 결과 일치하지 않는 경우 이웃한 위치에서 최적일 수 있으므로 두 경우 모두 비교한다)

 

이 방식으로 간신히 시간 내에 문제를 풀 수 있었다.

 

깨달은 점

처음부터 너무 어렵게 접근하지 말고 일단 주어진 조건 내에서 풀 수 있을 정도의 성능이라면 시도해보자