JAVA 백준2470 두 용액(BOJ2470)

문제링크 : https://www.acmicpc.net/problem/2470

2470번: 두 용액

N의 최대값이 100000이므로 2중 for문의로 풀 경우 시간 초과가 된다.

그래서 이분탐색으로 하면 통과할수있....지만 나같은 알린이는 죄다 처음 접하는 유형이라 많이 해메다가

검색찬스를 썻다...알고나면 이렇게 간단한걸.. 다음에 비슷한 유형은 절대 헤매지 말아야지

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

public class Main {
    static FastReader scan = new FastReader(); // 입력
    static StringBuilder sb = new StringBuilder(); //제출답안

    static int N, solutionA, solutionB, minValue;
    static int[] solutions;

    static void input() { //입력함수
        N = scan.nextInt();

        solutions = new int[N];

        for(int i = 0; i< N; i++) {
            solutions[i] = scan.nextInt();
        }

    }

    public static void main(String[] args) {
        input(); // 입력
        minValue = Integer.MAX_VALUE;

        //정답용액 찾기
        findSolution();

        System.out.println(sb.toString());

    }

    public static void findSolution() {

        Arrays.sort(solutions);

        int start = 0;
        int end = N-1;
        //양 끝단에서부터 좁아지면서 탐색
        while (start < end) {
            int sum = solutions[start] + solutions[end];
            //두 값의 절대값 차이가 기존보다 작을때 (=0에 더 가까울때)
            if(Math.abs(sum) < minValue) {
                minValue = Math.abs(sum);
                solutionA = solutions[start];
                solutionB = solutions[end];

            }
            //정렬된 상태에서 진행했기때문에 sum이 양수면 end절대값이 start절대값보다 크고
            //sum이 음수면 start절대값이 더 크다 그래서 상황에 맞게 더하고 빼며 절대값차이가 0에 가깝게 된다.
            if(sum > 0) {
                end--;
            } else {
                start++;
            }
        }

        sb.append(solutionA + " " + solutionB);
    }


    //류호석 강사님 템플릿
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}