백준 - 2470 두 용액(Java)

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

2470번: 두 용액

 

투포인터 문제입니다.

투포인터란, 말 그대로 두 개의 포인터를 사용해 문제를 해결하는 방식입니다. 

두 개의 포인터는 배열의 인덱스 번호로 사용합니다.

투포인터는 크게 두 가지로 탐색 방법을 나눌 수 있습니다.

1. 2개의 포인터가 다른 위치에서 시작하여 서로에게 다가가는 방향(정렬된 배열에서 주로 사용됨)
2. 2개의 포인터가 같은 위치에서 시작하여 같은 방향으로 탐색

위 문제의 경우 1번을 통해 해결할 수 있습니다.

 

문제 설명은 길지만, 요약하면 다음과 같습니다.

-> 정수 배열이 주어졌을 때, 두 합이 최대한 0에 가깝게 만드는 두 원소를 오름차순으로 출력하시오.

 

주어진 배열을 정렬하고 양 끝에서 포인터를 움직여 합을 최대한 줄여나가면 됩니다.

 

예를 들어 설명하겠습니다.

배열 {-11, 3, 5, -55, 99}가 있다고 가정하겠습니다.

우선 이 배열을 정렬하면 {-55, -11, 3, 5, 99}와 같습니다.

두 포인터를 사용할 것인데, 처음 위치를 양 끝에 잡습니다.

두 개의 포인터 합은 44입니다.

합이 44이기 때문에 0에 가까워 지기 위해서는 합의 숫자를 줄여야 합니다.

합의 숫자를 줄이기 위해서는  큰 것을 줄여야겠죠?

그렇기 때문에 High Pointer를 왼쪽으로 이동시켜야 합니다

이제 두 개의 포인터 합은 -50 이므로 숫자를 늘려야 합니다.

그렇기 위해서는 작은 것을 늘려야 겠죠?

그렇기 때문에 Low Pointer을 오른쪽으로 움직입니다.

이제 합은 -6이 되었습니다. 

아직 0보다 작기 때문에

Low Pointer를 한 번더 움직입니다.

합은 8이 되었습니다.

여기서 한 번더 움직이면 두 개의 포인터가 교차되기 때문에 더이상 움직일 수 없습니다.

 

지금까지 두 원소의 합은 순서대로 {-44, -50, -6, 8}가 나왔습니다.

문제에서 "0에 가까운"이라 했으니 절대값으로 확인해야 합니다.

즉, 정답은 -6이 도출되는 {-11, 5}가 정답입니다.

[구현 코드]

import java.io.*;
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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz;

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

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

        Arrays.sort(arr);

        int lp = 0;
        int hp = n-1;

        int ansLp = lp;
        int ansHp = hp;

        int tmp = Math.abs(arr[lp] + arr[hp]);

        while (lp < hp){
            int s = arr[lp] + arr[hp];

            if(s == 0) {
                ansLp = lp;
                ansHp = hp;
            }

            // 0에 더 가깝다면
            if(Math.abs(s) < tmp){
                tmp = Math.abs(s);
                ansLp = lp;
                ansHp = hp;
            }

            if(s > 0){
                hp--;
            }else{
                lp++;
            }
        }

        bw.write(arr[ansLp] + " " + arr[ansHp]);

        bw.flush();
        bw.close();
        br.close();
    }
}