[JAVA] 백준 2470 두 용액

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

2470번: 두 용액

 

1. 서론

 

투 포인터 문제이다. 투 포인터의 개념은 알겠으나 문제만 보면 어떻게 응용해야 할지 모르겠어서 일부러 고른 문제이다.

덕분에 새로운 응용 방법을 배우게 된 효자 문제.

 

2. 문제 풀이

 

엄청나게 길게 써있지만 결국엔 그냥 배열에 있는 값 중 두 개를 골랐을 때 그 답이 0이거나 0에 가장 가까운 두 값을 출력하는 것이 문제이다. 그리고 이 모든 것에 해당되지 않는다면 SAD라고 출력한다.

 

이 두 값을 선택하는 것을 투 포인터로 해야 하는데 사실 유형을 보고 그 유형을 익히기 위해 고른 문제이기 때문에 아는 거지 아니었으면 몰랐을 것 같다. (그런 눈을 기르기 위해 골랐으니 어쩌면 당연함.)

 

 

반응형

 

 

 

그런데 내가 아는 투 포인터의 기본 개념은 포인터 두 개가 배열을 탐색해서 원하는 탐색값을 찾아내는 것. 이외에는 문제를 별로 안 풀어봐서 잘 몰랐다. 그래서 어떻게 응용하는 건지 인터넷을 뒤적거리다가 이 방법을 발견했다.

 

두 포인터의 시작점이 배열의 양끝으로 원하는 값보다 작다면 왼쪽의, 아니라면 오른쪽의 포인터가 이동해서 원하는 값을 구하는 방법이다. 그럼 이 방법을 이 문제에 적용해보자.

 

이 문제는 배열에 무작위의 값이 주어진다. 그리고 두 값의 합이 0이거나 최대한 0에 가까운 값을 구하는 것이다.

그래서 나는 배열을 정렬했다. 문제의 조건에서 음수, 양수가 둘 다 있고 그렇기 때문에 합이 0이 나올 수 있는 것이기 때문에 정렬을 하면 가장 큰 음수~ 가장 큰 정수 순으로 정렬이 된다. 그래서 그 양끝값에서 시작해 0보다 작으면 왼쪽을, 0보다 크면 오른쪽을 이동하면서 합을 구하고 그 두 값의 합과 0의 차가 작은 것이 최대한 0이 작은 값이라고 가정하고 문제를 풀었다.

 

 

 

반응형

 

 

 

3. 코드 설명

 

 

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

public class Main {

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

    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());

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

   Arrays.sort(a);

   int s = 0, e = n - 1, x = a[s], y = a[e], sum = a[s] + a[e];
   while (true) {
     int tmp = a[s] + a[e];
     if (Math.abs(sum - 0) > Math.abs(tmp - 0)) {
       sum = tmp;
       x = a[s];
       y = a[e];
     }

     if (tmp == 0) {
       x = a[s];
       y = a[e];
       break;
     }
     if (tmp > 0)
       e--;
     if (tmp < 0)
       s++;

     if (s == e) break;
   }

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

 

값들을 입력받고 정렬 후에 양 끝쪽에서 시작해 포인터가 가리키는 값의 합을 구하고 그 합과 0의 차가 작은 것을 최대한 작은 값이라고 가정했다. 그리고 0이 나온 경우는 그게 가장 답에 가까운 것이기 때문에 바로 break 해줬다.