Binary Search: 백준 세용액 - 2473

문제 유형

Binary Search

작성 코드

첫번째 시도

package KakaoCodingStudy.kakaoNov1;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
// 2473 세용액 1트
public class Main {
    static int N;
    static long[] given;
    static long minCombination;
    static List<Long> threeLiquids;

    public static int getIndex(long num) {
        int right = threeLiquids.size() - 1;
        int left = 0;
        int center;
        while (left <= right) {
            center = (left + right) / 2;
            if (threeLiquids.get(center) >= num) {
                right = center - 1;
            } else {
                left = center + 1;
            }
        }
        return left;
    }

    public static void input() {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        given = new long[N];
        threeLiquids = new ArrayList<>();
        minCombination = Long.MAX_VALUE;

        for (int i = 0; i < N; i++) {
            given[i] = sc.nextLong();
        }
    }

    public static boolean minCheck(List<Long> currentList) {
        long currentCombination = 0;
        for (long liquid : currentList) {
            currentCombination += liquid;
        }
        currentCombination = Math.abs(currentCombination);
        if (currentCombination < minCombination) {
            minCombination = currentCombination;
            return true;
        } else {
            return false;
        }
    }

    public static void pro() {
        // -2
        // -2 6
        // -97 -2 6 -> -93
        // (-97 -6 6) -> -97
        // (-97 -2 98) -> -2
        for (long candi : given) {
            int index = getIndex(candi);
            if (threeLiquids.size() < 3) {
                threeLiquids.add(index,candi);
            }
            if (threeLiquids.size() == 3) {
                List<Long> temp = new ArrayList<>(threeLiquids);
                if (index == temp.size()) index--;
                temp.set(index, candi);
                if (minCheck(temp)) {
                    threeLiquids.clear();
                    threeLiquids.addAll(temp);
                }
            }
        }
        System.out.println(threeLiquids);
    }

    public static void main(String[] args) {
        input();
        pro();
    }
}

 

두번째 시도

package KakaoCodingStudy.kakaoNov1;

import java.util.Arrays;
import java.util.Scanner;
// 2473 세용액트 2트
public class Main {
    static int N;
    static long currentMin;
    static long[] given;
    static long[] answer;

    public static void input() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        given = new long[N];
        answer = new long[3];
        currentMin = Long.MAX_VALUE;

        for (int i = 0; i < N; i++) {
            given[i] = sc.nextLong();
        }
        Arrays.sort(given);
    }

    public static void pro() {
        for (int i = 0; i < N - 2; i++) {
            binarySearch(i);
        }
        Arrays.sort(answer);
        StringBuilder temp = new StringBuilder();
        temp.append(answer[0]).append(" ").append(answer[1]).append(" ").append(answer[2]);
        System.out.println(temp);
    }

    public static void binarySearch(int index) {
        int left = index + 1;
        int right = given.length - 1;

        while (left < right) {
            long sum = given[left] + given[right] + given[index];
            if (Math.abs(sum)< currentMin) {
                currentMin = Math.abs(sum);
                answer[0] = given[left];
                answer[1] = given[right];
                answer[2] = given[index];
            }
            if (sum > 0) {
                right--;
            } else {
                left++;
            }
        }
    }

    public static void main(String[] args) {
        input();
        pro();
    }
}

접근방식

첫번째 시도 - 직전에 푼 문제 증가하는 가장긴 부분수열2에서 증가하는 부분수열에서 이분탐색을 했다는 점에서 여기서도 활용이 가능하다고 판단했다. 하지만 문제가 있었다. 증.가.분수열2의 경우 수열이 증가해도 문제가 되지 않았으나 여기서는 정답의 길이가 3으로 한정돼있기 때문에 하드코딩으로 문제를 해결해야 했다. 그래서 그러한 이유로 문제 해결에 있어 예전에 풀었었던 두용액 문제를 활용하여 풀기로 했다.(틀리기도 했다.)

두번째 시도 -이번의 경우에는 이분탐색의 범위를 선정하여 index를 기준으로 왼쪽 오른쪽을 하나씩 비교하며 슬라이딩 도어처럼 옮겨가는 식으로 비교해갔다. 왼쪽이 움직일지 오른쪽이 움직일지는 총합이  양수일경우 오른쪽을 작게 총합이 음수일 경우 왼쪽을 크게 하는 식으로 옮겼다. 이분탐색은 이미 정렬이 돼있는 상태라 방금과 같은 방식이 적합하다고 생각했다.