[백준-골드]두 용액 (BOJ 2470)

문제

두 용액 링크

 

풀이

N은 최대 10^5 이기에 n^2 알고리즘은 안되서 처음에는 이진 탐색을 이용하려고 생각했으나 투 포인터를 이용하면 더 빠르게 값을 찾을 수 있을 것 같아 투 포인터로 문제를 해결했다.

 

코드

package org.algorithm.baekjoon.silver;

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

public class 두_용액 {
    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());

        long[] arr = new long[N];

        for(int i = 0; i < N; i++) {
            arr[i] = Long.parseLong(st.nextToken());
        }

        Arrays.sort(arr);
        int left = 0;
        int right = N - 1;

        long closestSum = Long.MAX_VALUE; 
        long[] result = new long[2];

        while (left < right) {
            long sum = arr[left] + arr[right];

            if (Math.abs(sum) < closestSum) {
                closestSum = Math.abs(sum);
                result[0] = arr[left];
                result[1] = arr[right];
            }

            if (sum < 0) {
                left++;
            }
            else {
                right--;
            }
        }

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

}