[BOJ] 2470. 두 용액

[작성일]

• 2022-03-15

[분류]

• 투포인터
  
  
  

[문제링크]

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

[요구사항]

두 용액 합이 0에 가장 가까울 때 두 용액을 구해라.

[풀이]

아주 정석적인 투포인터 문제이다.
우선 배열을 오름차순으로 정렬한다.
이제 i = 0, j = n-1로 양 끝점을 포인터로 잡고 시작한다.
arr[i] + arr[j] 의 절대값이 이때까지 구한 최소 값보다 더 작으면 갱신해준다.
이후, 두 수를 더한 값이 양수이면 더 줄여야하기 때문에 j--를 해주고,
음수이면 더 늘려야하기 때문에 i++해준다.
i랑 j가 만나게 되면 종료해준다.

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;


class Main {
    static int N;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());

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

        int i = 0, j = N - 1;
        int ans = Integer.MAX_VALUE;
        int v1 = 0, v2 = 0;

        while (i < j) {
            int sum = arr[i] + arr[j];
            int val = Math.abs(arr[i] + arr[j]);

            if(val < ans) {
                ans = val;
                v1 = arr[i];
                v2 = arr[j];
            }

            if(sum >= 0) {
                j--;
            } else {
                i++;
            }
        }

        System.out.println(v1 + " " + v2);
    }
}