[백준/2470] 두 용액 (Java)

Question

• 문제 링크 : https://www.acmicpc.net/problem/2470
• 분류 : 이진탐색
• 풀이 시간 : 40분

문제 해설

1. 많은 종류의 산성 및 알칼리성 용액 보유
2. 각 용액은 용액의 특성을 나타내는 하나의 정수가 주어짐
   1. 산성 용액 특성 : 1 ~ 1,000,000,000
   2. 알칼리성 용액 특성 : -1 ~ -1,000,000,000
3. 두 용액의 혼합 특성값 : 혼합에 사용된 각 용액의 특성값의 합
4. 두 용액 혼합하여 특성값이 0에 가장 가까운 용액 만들려고 함
5. 용액은 산성+산성, 산성+알칼리성, 알칼리성+알칼라성 모두 혼합 가능
6. 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액은?

Solution

풀이 접근 방법

1. 두 용액 혼합하여 특성값이 0에 가장 가까운 용액

   1. ~에 가장 가깝게 = 절댓값으로 비교

2. 용액의 수 : 2 이상, 100000 이하

   1. 두 용액의 합을 조합으로 구하면 시간초과
   2. 이분탐색으로 범위 좁혀가기

3. 이분탐색할 것 = 두 용액

   1. 용액 배열 오름차순 정렬
      1. 맨 왼쪽 : (제일) 작은 값
      2. 맨 오른족 : (제일) 큰 값
   2. 두 용액의 합의 절댓값으로 0에 가장 가까운지 비교
   3. 두 용액의 합 > 0 = 오른쪽 값이 왼쪽보다 큼 -> 합의 값 줄이기 위해 오른쪽범위 줄임
   4. 두 용액의 합 <= 0 = 왼쪽 값이 오른쪽보다 큼 -> 합의 값 늘리기 위해 왼쪽범위 줄임

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {

  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    int N = Integer.valueOf(br.readLine());
    int[] list = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

    Arrays.sort(list);
    int[] result = calculateArr(list, N);

    bw.write(result[0] + " " + result[1] + "\n");
    bw.flush();
    bw.close();
  }

  static int[] calculateArr(int[] list, int N) {
    int start = 0;
    int end = N - 1;
    // 두 수가 모두 양수 최대값일 때 나올 수 있는 값
    int maxDiff = 2000000000;
    int[] result = new int[2];

    while (start < end) {
      int sum = list[start] + list[end];

      // 0에 더 가까운 수를 찾기 위함이니까 절댓값으로 비교한다
      if (Math.abs(sum) < maxDiff) {
        result[0] = list[start];
        result[1] = list[end];
        maxDiff = Math.abs(sum);
      }

      // 이분탐색할 것 = 배열 안에서 숫자들의 합
      // 합이 0보다 크다는 것 = end번째 수의 절댓값이 start번째 수의 절댓값보다 크다는 의미
      if (sum > 0)
        // end(인덱스) 줄여주기
        end--;
      else
        // start(인덱스) 증가시키기
        start++;

    }

    return result;
  }

}