[백준] Q2473 세 용액 JAVA

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

2473번: 세 용액

 

1. 문제 이해 및 유형

투 포인터, parametric search, 정렬

https://www.acmicpc.net/problem/2470( 백준- 용액 ) 문제를 풀고 풀어보는 것도 도움이 된다.

 

용액의 특성 값이 -1000000000 ~ 1000000000까지의 정수로 주어진다.

세개를 택하여 합했을 때 0 에 가장 가까운 세 값을 구하시오.

 

정렬된 값에서의 합이 가장 낮은 값과 가장 큰 값을 더했을 때 그 합이 기준 값보다 크다면

그 합을 조금 낮춰주기 위해 큰 값을 낮추고, 값보다 작다면 합을 키워주기 위해 낮은 값을 높은 값으로

순차적으로 움직이면서 확인할 수 있기 때문에 투 포인터 또는 정렬된 값에서 빠르게 탐색이 가능한

이분탐색이라고 생각했다.

 

2. 문제 접근

이전에 '용액' 문제에서 기준 값 '0' 에 대해 문제를 풀었다. 이번에는 '세 용액'이기 때문에

그 기준 값이 0이 아니다. 대신 그 기준값을 어떠한 정해진 값 x로 두고 문제를 풀게 되면

x low right 라는 세가지 값이 정해진다.

 

x low right인 이유는 순차적으로 가장 낮은 값 x를 두고 x보다 위에 범위를 체크하여 

low x right과 같은 값이 없도록 보장하기 위해 순서를 맞춘 것이기 때문에

탐색의 범위는 기준 값 x의 index보다 +1 ~ 마지막 데이터가 될 것이다.

 

어떠한 조건을 만족하는 func을 기준으로 true 이거나 false인 상황에 따라 구분되면서 찾아간다는 점과

정렬된 값에서 탐색한다는 점에서 parametric search라고 생각했다.

 

그 기준은 두 용액 data[left] + data[right]가 기준 값 x와 합하였을 때 0보다 큰지, 작은지를 비교하기 위해서이다.

data[left] + data[right] + x > 0 이라면 값이 크기 때문에 큰 값 right 를 낮춰주고 

data[left] + data[right] + x < 0 이라면 값이 작기 떄문에 작은 값 left를 높여준다.

이때 x를 넘기면 data[left] + data[right] > -x 인데 함수로 사용할 때 func(int x)의 기준값을 x가 아닌 -x로 전달해준다.

 

또한, 마지막 left가 <0인 경우에 도달하게끔 하여야 모든 case들을 다볼 수 있고 case들을 보면서 값을 갱신해준다.

왜냐하면 data[left]+data[right] +x = 1이고 움직인 이후에 data[left] + data[right] + x = -2일 때 멈추어야

1인 경우 또한 확인이 가능하기 때문이다.

parametric serach func

정리)

 1. 들어온 값 오름차순 sorting

 2. 가장 낮은 값부터 기준 값 x로 두고 차례차례 확인한다. (length -2까지, 3개를 보장한다)

   2-1. x의 위치를 idx라고 할 때 폐구간 [idx+1, legnth-1]에서 확인한다.

   2-2. 어떠한 func( data[left] + data[right] + x < 0)이라면 left를 증가

   2-3. >=0 이라면 right를 증가시켜준다.

   2-4. 동시에 data[left] + data[right] + x의 절댓값이 가장 작은 값인지 확인하고 값을 갱신해준다.

/*
2022.01.13
문제번호 : Q2473
이름 및 난이도 : 세 용액 Gold IV
문제이해 
-----------------
세 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어 내시오.

제한 조건 : 

접근 방법 :
이전에 풀었던 두용액을 풀었던 것을 생각함.
하나를 집고 두용액을 만드는 방법으로 
지정한 x값을 만든다고 생각하면 된다. 
이번엔 BinarySearch로 풀어보자.
a   b|c
a+b < x인 값. 중 가장 큰 값.
a+c > x인 값.
binarysearch의 영역 [a,b] 포함
*/

import java.io.*;
import java.util.*;

public class Main {
    static long[] data;
    static long[] ans;
    static long min = Long.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        input();
        solution();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        data = Arrays.stream(br.readLine().split(" ")).mapToLong(Long::parseLong).sorted().toArray();
    }
    
    public static void solution() {
        min = Integer.MAX_VALUE;
        ans = new long[3];
        for (int i = 0; i < data.length - 2; i++) {
            long x = data[i];
            binarySearch(i+1, data.length-1, -x);
            //min = Math.min(min, Math.abs(binarySearch(i + 1, data.length - 1, x)));
        }
        //System.out.println(min);
        for(int i =0;i<3;i++){
            System.out.print(ans[i] + " ");
        }
        System.out.println();
    }

    public static void binarySearch(int left, int right, long target) {
        int l = left;
        int r = right;
      //A+B == -x(==x)
        while(l<r){
            long sum = data[l] + data[r];
            if(Math.abs(sum-target) < min){
                min= Math.abs(sum-target);
                ans[0] = -target;
                ans[1] = data[l];
                ans[2] = data[r];
            }
            if(sum < target){
                //data[l] + data[r] + x < 0
                l++;
            }else{
                r--;
            }
        }

    }
}