[백준 2473] 세 용액 - JAVA

문제

문제 정의

• $N$개의 용액이 주어지고 각 용액의 특성값이 주어졌을 때
• 이 중 세 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 세 용액 구하기

예시

---

접근 방법

두 방법으로 풀 수 있고
투 포인터를 사용하는 것이 시간 복잡도가 빠르지만
이번에는 이분 탐색 학습을 위해 1번 방식으로 문제를 풀었습니다.

---

핵심 로직

1. 용액 특성값 정렬하기

투 포인터이던 이분 탐색이던 알고리즘을 사용하려면 정렬해야 합니다.
가장 먼저 해야할 것은 solutions배열의 정렬입니다.

---

2. 두 용액을 고정하고 이분탐색

두 용액을 고정하고 하나의 용액이 0에 가장 가깝도록
이분 탐색을 수행합니다.

• 두 개의 용액을 이중 for문으로 선택한 후 twoSolutions 변수에 더해줍니다.
• 이분 탐색을 수행하는데 0이 되는 경우에는 바로 정답을 반환합니다.
• 아닌 경우에는 이분 탐색을 통해 0에 가장가까운 세 용액에 대해 최솟값 갱신 로직을 수행합니다.

---

이분 탐색.. TLE 발생하지 않나요?

---

정리

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
    static StringTokenizer st;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        long[] solutions = new long[N];
        for (int i = 0; i < N; i++) {
            solutions[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(solutions);
        sol(N, solutions);
    }

    static void sol(int N, long[] solutions) {
        long min = Long.MAX_VALUE;
        long[] answer = new long[3];

        for (int i = 0; i < N-2; i++) {
            for (int j = i + 1; j < N-1; j++) {
                long twoSolutions = solutions[i] + solutions[j];

                int s = j + 1;
                int e = N - 1;

                while (s <= e) {
                    int m = (s + e) / 2;
                    long checkMin = Math.abs(twoSolutions + solutions[m]);

                    if (twoSolutions + solutions[m] == 0) {
                        System.out.println(solutions[i] + " " + solutions[j] + " " + solutions[m]);
                        return;
                    }

                    if (checkMin < min) {
                        min = checkMin;
                        answer[0] = solutions[i];
                        answer[1] = solutions[j];
                        answer[2] = solutions[m];
                    }


                    if (twoSolutions + solutions[m] > 0) e = m - 1;
                    else s = m + 1;
                }
            }
        }

        System.out.println(answer[0] + " " + answer[1] + " " + answer[2]);
    }
}