[백준 9024] 두 수의 합 - JAVA

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

 

이분 탐색으로 풀었다. (투 포인터가 나을 것 같다.)

 

예제 및 설명에서,

 K = 4 에 그 합이 가장 가까운 두 정수는 {-7, 12}, {9, -4}, {5, -2}, {5, 0}, {1, 2} 등의 다섯 종류가 있다.

이 때 "가장 가까운 값"은 3, 5 둘 다 될 수 있다. 음수도 고려해야 하므로 탐색 기준을 세우는게 까다로웠다.

 

1. 포인터를 옮기는 기준 세우기

이분 탐색을 적용하려면, 값을 순차적으로 좁힐 수 있는 기준이 필요하다. 

 

diff = 두  원소의 합과 K의 거리 = Math.abs(K - 원소의 합) 로 놓으면,

 

원소의 합 < K일 때

원소의 값을 올려야한다.

 

원소의 합 > K일 때

원소의 값을 내려야 한다.

 

2. 이분탐색 적용하기

한 원소를 a[i]로 미리 뽑아놓는다.

 

이후 나머지 원소를

st = i+1, ed = N-1의 범위에서 이분탐색으로 찾는다.

 

복잡도는 O(nlogn(정렬) + n(모든 i에 대해) * logn(이분 탐색) = O(nlogn)이다. 

이는 midVal을 구하는 과정에서 a배열을 O(n)으로 전체 탐색하지 않으므로 가능하다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

  public static void main(String args[]) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stn;

    int T = Integer.parseInt(br.readLine());
    for (int tc = 0; tc < T; tc++) {

      stn = new StringTokenizer(br.readLine());
      int N = Integer.parseInt(stn.nextToken());
      int K = Integer.parseInt(stn.nextToken());

      int[] a = new int[N];
      stn = new StringTokenizer(br.readLine());

      for (int i = 0; i < N; i++) {
        a[i] = Integer.parseInt(stn.nextToken());
      }
      Arrays.sort(a);

      int min = Integer.MAX_VALUE;
      int cnt = 0;

      for (int i = 0; i < N - 1; i++) {

        int st = i + 1;
        int ed = N - 1;
        int base = a[i];

        while (st <= ed) {
          int mid = (st + ed) >>> 1;

          int midVal = base + a[mid];
          int diff = Math.abs(K - midVal);

          if (diff < min) {
            cnt = 1;
            min = diff;
          } else if (diff == min) {
            cnt++;
          }

          if (midVal < K) {
            st = mid + 1;
          } else {
            ed = mid - 1;
          }
        }
      }
      System.out.println(cnt);
    }
  }
}