백준 2467번 용액 (JAVA)

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

2467번: 용액

 

 

저는 처음에 2중 for문으로 문제를 해결하려 하였습니다. 하지만 n의 최대가 100,000여서 시간 초과가 나왔습니다.

다음으로는 투 포인트를 생각하였습니다.

처음과 끝을 가리키게 하고 둘 중 절대값이 큰 값의 인덱스를 줄여나가면서 절대값 합이 최소인 것을 찾아 나갔습니다.

저는 가장 낮은 값과 가장 큰 값을 더해가면서 가장 낮은 값을 올리고 가장 큰 값은 줄이는 방식을 생각하였습니다. 

그래서 처음에 맨 앞과 맨 뒤를 포인터로 가리키고 절대값이 큰 값을 인덱스를 가운데로 가도록 구현하였습니다.

절대값이 작은 것을 가운대로 오게하면 한번 작아진 값이 계속 작아질 것이기 때문에 절대값이 큰 값으로 하였습니다.

 

 

 

package BOJ.TwoPoint;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_2467 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(st.nextToken());
        int[] input = new int[n];
        st = new StringTokenizer(br.readLine());
        int nearZeroValue = 2_000_000_000;
        int[] result = new int[2];
        int si = 0;
        int ei = n-1;
        for(int i = 0 ; i < n ; i++){
            input[i] = stoi.apply(st.nextToken());
        }
        while(true){
            if(si == ei) break;
            int sum = input[si] + input[ei];
            int absSum = Math.abs(sum);
            if(nearZeroValue > absSum){
                nearZeroValue = absSum;
                result[0] = input[si];
                result[1] = input[ei];
            }
            if(sum < 0){ //
                si++;
            }else{
                ei--;
            }
        }
        System.out.printf("%d %d\n",result[0],result[1]);
    }
}