[Java] 백준 2467번 : 용액

문제

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

 

접근 방법

1. 음수인 알칼리 용액과 양수인 산성 용액을 더해서 0이랑 최대한 가까이 만드는 것이 문제다.
2. 따라서 브루트포스로 문제를 푼다면 N값이 10만이므로 시간초과가 발생할것을 생각했다.
3. 그래서 이 문제를 투포인터로 풀면 된다고 생각했다.

코드

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

public class Main {
    private static StringBuilder sb;
    private static BufferedReader br;
    private static StringTokenizer st;
    private static int N;
    private static int[] arr;
    private static long min = Long.MAX_VALUE;
    private static int left,right;

    //입력
    public static void input() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        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());
        }
    }

    //실행
    public static void process() {
        int s = 0;
        int e = N-1;

        while(s<e){
            long sum = arr[s]+arr[e];
            
            //만약 0 이 나온다면 더 볼필요 없다.
            if(Math.abs(sum) == 0){
                sb.append(arr[s]+" "+arr[e]);
                return;
                
             //0이 아니지만 min값보다 작다? 그럼 교체
            }else if(Math.abs(sum)<min){
                min = Math.abs(sum);
                left = s;
                right = e;
            }
            
            sum값이 음수이면 내 왼쪽에 있는 어느것을 더해도 음수값만 커진다.
            if(sum<0){
                s++;
            }else{
                e--;
            }
        }
        //여기까지 온다는건 둘이 합쳤을때 0은 아니지만 0이랑 최대한 가까운 값
        sb.append(arr[left]+" "+arr[right]);
    }


    public static void main(String[] args) throws Exception {
        input();
        process();
        System.out.println(sb.toString());
    }
}