[백준] 2467 용액 - 투포인터 JAVA

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

2467번: 용액

코드설명

투포인터를 활용하여 진행합니다.

 

시간복잡도를 보면,

만약 단순히 for문으로 두 합의 값이 가장 0에 가까운 것을 찾으려면 O(N*N) = 100,000 * 100,000 = 10,000,000,000 의 시간복잡도가 나오기에 투포인터 알고리즘과 이분탐색을 활용하여 시간복잡도를 줄여야합니다.

 

투포인터 알고리즘의 시간복잡도는 O(N) 입니다. 해를 최악으로 N번의 탐색으로 알 수 있습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int N;
	public static int[] arr;
	public static int answer = Integer.MAX_VALUE;
	public static int start = 0, end = 0;
	public static int startIdxAnswer = 0, endIdxAnswer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
 
    	arr = new int[N];
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken()); 
    	}
    	
    	twoPointer();
    	
    }
    public static void twoPointer() {
    	int start = 0; //용액의 Idx값
    	int end = N-1; //용액의 Idx값
    	
    	while(start < end) {
    		int value = arr[start] + arr[end];
    		
    		if(answer > Math.abs(value)) { //0이랑 더 가까운 값이라면,
    			answer = Math.abs(value);
    			startIdxAnswer = start;
    			endIdxAnswer = end;
    		}
    		
    		if(value == 0) {
    			break;
    		}
    		
    		if(value < 0) { //0보다 작을경우 더 큰값을 더해줘야합니다.
    			start += 1;
    		}
    		else if(value >= 0) { //0보다 클경우 더 작은값을 더해줘야합니다.
    			end -= 1;
    		}
    		
    	}
    	System.out.println(arr[startIdxAnswer]+" "+arr[endIdxAnswer]);
    }
  
}