[백준 / Java] 2467번 용액

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

2467번: 용액

문제 유형

• 투 포인터
• 이진 탐색
  
  

문제 풀이

전체 용액의 수 N의 범위가 2 이상 100,000 이하의 정수이므로, 완전 탐색을 이용해서 풀 수 없다.
따라서 O(NlogN) 의 시간복잡도 문제를 해결해야 하는데, 다행스럽게도 입력 데이터가 이미 오름차순 정렬되어 있다!
이를 이용하여 문제를 해결하기 위한 가장 직관적인 방법은 투 포인터이며, 이외에도 이진 탐색을 이용해서 풀 수 있다.

투 포인터

투 포인터는 말 그대로 리스트나 배열에 두 지점을 지정하여, 조건에 따라 두 지점을 각각 이동시켜 원하는 값을 얻는 방법이다.
문제에서는 가장 작은 값과 가장 큰 값을 각각 지점으로 지정한 뒤, 서로 가운데를 향하여 이동시켜 0에 가장 가까운 수를 구하면 된다.

1. 0과 N-1를 각각 투 포인터로 지정(left, right로 표현)
2. 각 지점의 수를 비교하여 합이 0에 가장 가까운 수를 구함
    - min > arr[left] + arr[right] 의 절댓값 : min(최솟값) 갱신
    - arr[left] + arr[right] >= 0 : right 포인터를 왼쪽으로 이동시켜 값을 감소시킴 → right--
    - arr[left] + arr[right] < 0 : left 포인터를 오른쪽으로 이동시켜 값을 증가시킴 → left++

소스 코드

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

class Main {

  int n;
  int[] arr = new int[100000];
  int min = Integer.MAX_VALUE;
  int[] answer = new int[2];

  public static void main(String[] args) throws Exception {
    new Main().solution();
  }

  public void solution() throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    n = Integer.parseInt(br.readLine());

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

    int left = 0;
    int right = n - 1;
    while (left < right) {
      int sum = Math.abs(arr[left] + arr[right]);

      if (sum < min) {
        min = sum;
        answer[0] = arr[left];
        answer[1] = arr[right];
      }

      if (arr[left] + arr[right] >= 0) {
        right--;
      } else {
        left++;
      }
    }

    for (int a : answer) {
      System.out.print(a + " ");
    }
  }
}

 

이진 탐색

전반적인 아이디어는 투 포인터와 동일하다.
N개의 배열의 값을 0부터 N-2까지 순회하면서 이진 탐색을 수행한다.(N-1의 범위를 제외시키는 이유는 이진 탐색을 할때 동일한 값에 대해 탐색하기 때문에 수행할 필요가 없다.)
이진 탐색을 수행할 때, 현재 순회 값과 이진 탐색을 통해 얻은 중간값의 합이 0에 가장 가까운 수를 구해주면 된다.

1. 0과 N-2 범위에서 배열을 순회
2. 기준점을 arr[i]라고 할 때, i+1과 N-1사이에 있는 원소 중 기준점과의 합이 0에 가장 가까운 수를 구함
    - min > arr[left] + arr[right] 의 절댓값 : min(최솟값) 갱신
    - arr[mid] + arr[i] >= 0 : 기준점과 이진 탐색내 중간값 원소의 합을 감소시킴 → right = mid - 1
    - arr[mid] + arr[i] < 0 : 기준점과 이진 탐색내 중간값 원소의 합을 증가시킴 → left = mid + 1

소스 코드

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

class Main {

  int n;
  int[] arr = new int[100000];
  int min = Integer.MAX_VALUE;
  int[] answer = new int[2];

  public static void main(String[] args) throws Exception {
    new Main().solution();
  }

  public void solution() throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    n = Integer.parseInt(br.readLine());

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

    for (int i = 0; i < n - 1; i++) {
      int target = arr[i];
      binarySearch(i + 1, n - 1, target);
    }

    for (int a : answer) {
      System.out.print(a + " ");
    }
  }

  public void binarySearch(int left, int right, int target) {
    while (left <= right) {
      int mid = (left + right) / 2;
      int sum = Math.abs(arr[mid] + target);

      if (sum < min) {
        min = sum;
        answer[0] = target;
        answer[1] = arr[mid];
      }

      if (arr[mid] + target < 0) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
}