[백준] 2373번 세 용액

들어가며

두 용액을 이분탐색으로 풀어서 이 문제도 이분탐색으로 풀어야하나? 라는 생각이 당연하게 들었다. 근데 보통 left, right로 나눠서 3개의 포인터(?)를 가지고 답을 구해나가야하는데 이건 세가지인데? 이런 혼란이 생겼다. 그래서 아 그럼 2개씩 뽑아서 구한 조합의 합을 먼저 구하고 원본 배열 (nC2 + n) 합쳐서 이분탐색을 돌리면 3개의 합이 나오지 않을까? 라고 생각했다. 근데 3개의 원소를 어떻게 기록하지...
이처럼 생각이 많았던 문제이다. 브루트포스, 조합을 거쳐갔지만 결국 이분탐색으로 풀었다.

문제 풀이

우선 이분탐색이지만 주의할 점은 3개의 용액의 합을 비교해서 풀어야한다는 것이다. 그래서 2중으로 반복문이 돌아가겠지만 이분 탐색이므로 O(nlgn)이 될것으로 예상된다.

1. 먼저 0부터 n-2개까지 가장 바깥쪽의 반복문이 돌아간다.

-> 이때 n-2인 이유는 현재 인덱스 이후에 mid, right를 두어 세개의 합을 비교하려면 최대 n-2까지만 갈 수 있기 때문이다.

2. 안쪽 while문에서는 평소에 하던 이분 탐색을 돌린다.

-> 대신 파라미터로 들어온 현재 가장 바깥쪽 반복문의 인덱스가 left, left+1이 mid, 가장 마지막 인덱스가 right가 된다.

3. 세개의 합이 최솟값일 때 pick 배열에 값을 넣어주고, min 값을 변경해준다.

4.이후에 만약 세 개의 합이 0보다 크다면 right--(값을 줄여주기 위해), 그게 아니라면 left++(값을 늘려주기 위해)

전체 코드

private static int n;
private static long[] arr;
private static int[] pick = new int[3];
private static long min = Long.MAX_VALUE;
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    n = Integer.parseInt(br.readLine());

    arr = new long[n];
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 0; i < n; i++) {
        arr[i] = Long.parseLong(st.nextToken());
    }

    Arrays.sort(arr);

    for (int i = 0; i < n-2; i++) {
        solution(i);
    }

    Arrays.sort(pick);
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < 3; i++) {
        sb.append(arr[pick[i]]).append(" ");
    }
    System.out.println(sb);
}

private static void solution(int left) {
    int mid = left + 1;
    int right = arr.length - 1;

    while (mid < right) {
        long sum = arr[mid] + arr[left] + arr[right];
        long absSum = Math.abs(sum);

        if (absSum < min) {
            min = absSum;
            pick[0] = mid;
            pick[1] = left;
            pick[2]= right;
        }

        if (sum > 0) {
            right--;
        } else {
            mid++;
        }
    }
}