[백준] 2470 두 용액 - 투포인터(Two Pointer) JAVA

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

코드설명

투포인터를 활용한 문제입니다.

 

시간복잡도를 보면,

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

 

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

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	public static int N, M, K = 0;
	public static int[] arr;
	public static int answer0=0, answer1=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());
    	}
    	
    	Arrays.sort(arr);
    	twoPointer();
    }
    
    public static void twoPointer() {
    	int left = 0;
    	int right = N-1;
    	
    	int minDiff = Integer.MAX_VALUE;
    	while(left < right) {
    		
    		int a = arr[left];
    		int b = arr[right];
    		
    		int abs = Math.abs(a+b);
    		if(abs < minDiff) {
    			minDiff = abs;
    			answer0 = a;
    			answer1 = b;
    		}
    		
    		if( a + b > 0) { //합이 0 보다 크다면, 양수값을 줄여줍니다.
    			right -= 1;
    		}else if(a+b <= 0){ //합이 0보다 작다면, 음수값을 줄여줍니다.
    			left += 1;
    		}
    	}
    	System.out.println(answer0 +" "+answer1);
    }
    
    
}

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
 
public class Main {
	
	public static int N, M;
	public static int[] arr;
	public static long start = 0, end = 0;
	public static long answer = Integer.MAX_VALUE;
	public static long answerStart = 0, answerEnd = 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());
    	}
    	Arrays.sort(arr);
    	
    	twoPointer();
    	
    }
    
    public static void twoPointer() {
    	int start = 0;
    	int end = N - 1;
    	
    	while(start < end) { //용액은 2가지이므로 같아지면 안됨
    		int value = arr[start] + arr[end]; //일반값(투포인터 과정에서 어떤값을 계산해야할지 알려주는값)
    		int AbsValue = Math.abs(value); //절대값(0 보다 가까운지만 알면됨)
    		
    		
    		if(answer > AbsValue) { //절대값을 비교하여 0 보다 가까운지 알기 위함
//    			System.out.println(" "+arr[(int)answerStart]+" "+arr[(int) answerEnd]+" "+answer);
    			answer = AbsValue;
    			answerStart = start;
    			answerEnd = end; 
    		}
    		
    		if(value > 0) { //합이 0보다 크다면, 양수 값을 줄여줍니다.
    			end--;
    		}else if(value <= 0) { //합이 0보다 작다면, 음수값을 줄여줍니다.
    			start++;
    		}
    	}
    	
//    	System.out.println(" "+arr[(int)answerStart]+" "+arr[(int) answerEnd]+" "+answer);
    	System.out.println(arr[(int)answerStart]+" "+arr[(int) answerEnd]);
    }
    
}