투 포인터 활용 - BOJ 2470 두 용액

문제

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

2470번: 두 용액

 

 

 

문제 접근

• 두 수의 합이 0에 가장 가까워야 한다. 하지만 데이터가 음수와 양수로 나뉘어져 있기 때문에, 두 수의 합의 절댓값을 가지고 판단해야 한다.
• 데이터 값이 중구난방으로 되어있어 바로 처리하기가 곤란하다. 정렬을 해서 음수 파트와 양수 파트를 나누고 양 끝에서 두 개의 포인터를 사용하여 투 포인터 전략을 사용해야 한다.
• 두 수의 합의 절댓값을 계산한 후, 해당 절댓값이 지금까지 찾은 값 중 최소인가를 판단한 뒤, 최소라면 갱신을 한다. 이후 합이 양수라면 앞쪽이 음수인 특성 상 앞쪽을 올려도 합이 커지기 때문에 뒷쪽을 한 칸 내려야 한다.
• 합이 음수라면 뒷쪽을 내려도 합이 커지기 때문에 앞쪽을 한 칸 올려야 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

// 두 용액
public class StudyCode {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int[] data = new int[N];

        for (int i = 0; i < N; i++){
            data[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(data);

        long ans = Long.MAX_VALUE;
        long sum = 0L;
        long sum_abs = 0L;
        int[] result = new int[2];

        int start = 0;
        int end = N - 1;

        while(start < end){
            sum = data[start] + data[end];
            sum_abs = Math.abs(sum);

            if (ans > sum_abs){
                ans = sum_abs;
                result[0] = data[start];
                result[1] = data[end];
            }

            if (sum > 0){
                end--;
            } else{
                start++;
            }
        }

        System.out.println(result[0] + " " + result[1]);
    }
}

• 해당 투 포인터는 앞 뒤에서 시작하기 때문에 교차하는 지점이 끝나는 지점이다.