[JAVA] 백준 2470 두 용액

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

 

1. 서론

 

https://coding-log.tistory.com/267

[JAVA] 백준 2470 두 용액

 

이 문제는 예전에 투 포인터로 푼 적이 있는 문제이다. 하지만 이분 탐색을 공부하기 위해서 이분 탐색으로 풀어봤다.

예시를 보면 대강 맞는 것 같은데 1%에 틀려서 다른 풀이들도 보고 GPT한테 코드 좀 고쳐달라고 했는데 어쨌든 혼자서 풀지 못한 문제이다.

 

(그런데 블로그에 쓰여있는 거 보니까 예전이랑 문제가 바뀌었나? 웬 SAD 타령을 하네... 근데 웃긴 점 SAD 출력하는 코드도 안 작성되어 있음)

 

https://www.acmicpc.net/board/view/138413

 

<< 반례들 모여있는 링크

 

2. 문제 풀이

 

배열에 주어진 값 두 개를 골라서 더했을때 0에 가장 가까운 값을 두 개 구하는 문제이다.

 

아직 이분 탐색 유형이 익숙하지 않아서 뼈대코드를 보면서 조금씩 수정했을 때 예제 + 질문 게시판에 있던 반례들이 맞길래 그냥 냈는데 1%에서 틀렸다고 해서 황당했다.

 

틀린 코드)

 

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

public class Main {
  static int min, x, y;
  static int[] a;

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

    int n = Integer.parseInt(br.readLine());
    a = new int[n];

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

    Arrays.sort(a);

    min = Math.abs(a[0] + a[n - 1]); x = 0; y = n - 1;
    for (int i = 0; i < n - 1; i++)
      binary_search(i, n - 1);

    System.out.print(a[x] + " " + a[y]);
  }

  public static void binary_search(int left, int right) {
    if (min > Math.abs(a[left] + a[right])) {
      min = Math.abs(a[left] + a[right]);
      x = left; y = right;
    }

    while (left < right) {
      int mid = (left + right) / 2;

      if (Math.abs(a[mid] + a[left]) > min)
        left = mid + 1;
      else {
          min = Math.abs(a[mid] + a[left]);
          x = left; y = mid;
      }

      if (Math.abs(a[mid] + a[right]) > min)
        right = mid - 1;
      else {
          min = Math.abs(a[mid] + a[right]);
          x = mid; y = right;
      }
    }
  }
}

 

내가 생각했을 때는 그냥 left, right에 배열의 끝값들을 넣고, min과 비교하면서 left + mid, right + mid 값을 비교하며 값을 이동시켜 주고 최솟값을 갱신해야겠다.

 

=> 하지만 너무 투 포인터적인 코드이다. 그리고 내가 짰지만 왜 맞았으며, 왜 틀렸는지 잘 모르겠다 ㅎ

아마 left, right 를 한 번에 하나만 이동해야 하는데 양쪽 다 이동하는 것도 문제일 것이고, 값 비교하고 이동하는 게 틀렸을 것이다.

 

사실 구글링등을 통해서 많은 사람들의 코드를 봤지만 크게 와닿지가 않아서 제일 이해도가 높은 내 코드를 기반으로 GPT에게 수정을 요청했다.

 

 

 

반응형

 

 

 

 

GPT 논리)

 

public static int binary_search(int left, int right, int target) {
    int closest = left;  // 가장 가까운 값을 저장할 변수

    while (left <= right) {
      int mid = (left + right) / 2;

      // 현재 mid가 target에 더 가까우면 closest 갱신
      if (Math.abs(a[mid] - target) < Math.abs(a[closest] - target)) {
        closest = mid;
      }

      // target이 더 작으면 왼쪽으로 이동
      if (a[mid] < target) {
        left = mid + 1;
      }
      // target이 더 크면 오른쪽으로 이동
      else {
        right = mid - 1;
      }
    }

    return closest;
  }

 

target값은 비교하려는 배열의 값 중 한 가지의 -1을 곱한 값이다.

이분 탐색은 정렬이 되어있다고 가정하기 때문에 그 값의 다음 값인 i + 1번째 값부터 비교해서 답을 찾아내는 게 주요 논리이다.

 

mid의 값이 가장 0에 가까운 index인 closest의 값보다 더 작다면 closest를 갱신

 

정렬되어 있으므로 오름차순이기 때문에 target이 더 작으면 target과 가까워줘야 하기 때문에 큰 수를 얻기 위해 left를 옮기고,

그 반대면 작은 수를 얻기 위해 right의 범위를 옮겨서 탐색 범위를 좁힘

 

=> 이 탐색 범위를 좁히는 아이디어를 아직도 못 내겠다... 이것도 많이하며 dfs, bfs처럼 쉽게 할 수 있는 날들이 올까?

 

 

3. 코드 설명

 

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

public class Main {

  static int min, x, y;
  static int[] a;

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

    int n = Integer.parseInt(br.readLine());
    a = new int[n];

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

    Arrays.sort(a);

    min = Integer.MAX_VALUE;
    x = -1;
    y = -1;
    for (int i = 0; i < n - 1; i++) {
      int close = binary_search(i + 1, n - 1, -a[i]);
      int sum = Math.abs(a[i] + a[close]);

      if (sum < min) {
        x = i;
        y = close;
        min = sum;
      }
    }

    System.out.print(a[x] + " " + a[y]);
  }

  public static int binary_search(int left, int right, int target) {
    int close = left;

    while (left <= right) {
      int mid = (left + right) / 2;

      if (Math.abs(a[mid] - target) < Math.abs(a[close] - target))
        close = mid;

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

    return close;
  }
}

 

배열을 0번부터 n-1번까지 하나의 target으로 정하고 그와 가장 가까운 값을 찾아낸다.

그러기 위해 binary_search 함수를 작성했다.

left, right로 탐색 범위를 받고, target으로 그와 가장 가까운 값을 찾아줬다. (설명은 위에 2번 참조)

 

그리고 target값과 찾은 값을 더한 후 min을 갱신해줬다.