[백준] Gold V. 두 용액

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

 

사용 알고리즘

• 투 포인터
• 이분탐색

 

풀이

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

public class Main {
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

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

        Arrays.sort(arr);

        // -99, -2, -1, 4, 98

        // -100 1 2 100 10000
        int lo = 0;
        int hi = n - 1;
        long min = Integer.MAX_VALUE;
        int [] res = new int[2];

        while(lo < hi) {
            long sum = arr[lo] + arr[hi];
            if (Math.min(min, Math.abs(sum)) == Math.abs(sum)) {
                min = Math.abs(sum);
                res[0] = arr[lo];
                res[1] = arr[hi];
            }
            if (sum > 0) hi--;
            else lo++;
        }
        System.out.println(res[0] + " " + res[1]);
    }
}

 

 

회고

 

오전에 잠깐 풀 때는 안풀리다가 오후에 다시 시도하니 한번에 통과했다.

 

이분탐색 + 투포인터를 조합해서 풀었다. Array.sort로 O(nlogn), 투포인터로 O(n)이라 최종 시간복잡도는 O(nlogn)이고, n이 10만일 때도 1초안에 무사히 통과된다.

 

lo와 hi의 절댓값 합을 구한 다음에 작을 때 계속 갱신해주고, 합이 0보다 클 때는 상한점을 낮춰서 0에 가깝게 하고, 0보다 작을 때는 하한점을 높여 0과 가깝게 설정해서 풀이했다.