[백준/Java] 2467번 : 용액

✏️ 문제 탐색

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

 

산성 용액(1~1,000,000,000 양의 정수)

알칼리성 용액(-1~-1,000,000,000 음의 정수)

 

N개의 용액 중 두 개의 서로 다른 용액의 합이 0에 가장 가깝게 만들려고 한다.

이때 두 용액을 출력하라.

✏️ 구현 아이디어

용액이 최대 100,000개일 때 그 중 2개의 용액을 선택하는 경우는 100,000_P_2 = 100,000*99,999이다.

모든 연산을 제한 시간(1초) 안에 수행할 수 없다. 

따라서 용액 2가지를 찾을 때 이분 탐색을 사용해보자.

 

각 N개의 용액 마다 자신을 제외한 N-1개의 용액과 짝을 지은 후

합해서 0에 가장 가까운 값이 무엇인지 구한다.

 

예)

5
-99 -2 -1 4 98

 

N개의 용액이 이미 정렬되어있으므로 다시 정렬할 필요는 없음

 

-99에 대해서 합이 0과 가장 가까운 수가 뭔지 탐색해보자.

 

start=0, end=4, mid=2

-99+(-1)=-100 

합이 음수이므로 범위를 뒤로 조정

 

start=3, end=4, mid=3

-99+4=-95

합이 음수이므로 범위를 뒤로 조정

 

start=4, end=4, mid=4

-99+98=1

합이 양수이므로 범위를 앞으로 조정

 

start=5, end=4, mid=4

start>end이므로 탐색 종료

 

나머지 -2, -1, 4, 98에 대해서도 탐색을 진행한다.

전체 탐색 과정에서 두 용액의 합의 절댓값이 minDist보다 작으면 minDist와 그 때 두 용액의 위치를 갱신한다.

 

마지막으로 저장된 두 용액의 위치를 이용해서 두 용액의 값을 출력한다.

✏️ 알고리즘

이분탐색

✏️ 시간 복잡도

용액이 최대 100,000개, 용액 마다 약 log100,000번 탐색하므로

총 100,000*5번 연산 -> 제한 시간(1초) 안에 탐색 가능하다.

✏️ 오답 노트

탐색 범위를 조정하는 조건을 '두 용액의 합이 양수인지/음수인지'가 아니라

'두 용액의 합이 0에서 더 멀어졌는지/가까워졌는지'로 두고 풀어서 틀렸다.

 

N개의 용액이 음수와 양수가 섞여있을 수도 있고, 음수 또는 양수로만 이루어져있을 수도 있어서

이분 탐색 시 하위 조건문으로 음수/양수를 나눠야 하나 생각했는데 아니었다.

✏️ 코드 설계

1. 입력 받기 (용액의 특성값이 최대 1,000,000,000이 될 수 있으므로 long타입 사용)
2. 현재까지 용액 합의 절댓값 중 가장 작은 값을 저장하는 minDist 선언
3. minDist가 갱신될 때마다 두 용액의 위치가 어디인지 저장하는 ans[] 선언
4. 0~N-1 용액 마다 이분 탐색 (start=i+1, end=N-1)
   
   1. mid, sum, dist를 계산
   2. sum이 양수이면 앞으로 범위 조정
   3. sum이 음수이면 뒤로 범위 조정
   4. minDist>dist이면 minDist, 두 용액의 위치 갱신
5. 마지막으로 갱신된 두 용액의 특성값을 출력

✏️ 정답 코드

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

public class Main{
    static int N;
    static long[] liq;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        //입력 받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

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

        long minDist = Long.MAX_VALUE;
        int[] ans = new int[2];

        for(int i=0; i<N-1; i++){
        	//0번째 용액부터 N-2번째 용액까지 탐색하며
            //본인을 제외한 용액과의 합이 0과 가까운 용액이 무엇인지 찾기
            int start = i+1;
            int end = N-1;

            while(start <= end){
                int mid = (start+end)/2;

                long dist = Math.abs(liq[mid] + liq[i]);
                long sum = liq[mid] + liq[i];

                if(dist < minDist){
                    minDist = dist;
                    ans[0] = i;
                    ans[1] = mid;
                }

                if(sum < 0){
                    //합이 음수면 뒤로 범위 조정
                    start = mid + 1;
                }else{
                    //합이 양수면 앞으로 범위 조정
                    end = mid - 1;
                }
            }
        }
        Arrays.sort(ans);
        System.out.println(liq[ans[0]] + " " + liq[ans[1]]);

    }

}