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

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

2473번: 세 용액

코드설명

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

 

시간복잡도를 보면, 

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

 

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

추가로, 하나의 용액을 고정적으로 사용하고 정렬을 한번 진행하므로 O(N * N)의 시간복잡도를 가집니다.

 

코드 로직입니다.

1. 배열을 오름차순으로 정렬합니다.
2. 한 용액을 확정적으로 선택하고, 나머지 두 용액을 선택하는데 사용할 투 포인터를 초기화합니다. 주요 반복문은 N-2번 실행됩니다.
3. 투 포인터를 이용하여 세 용액의 합을 계산하고, 이 값이 0에 가장 가까운지 확인합니다. 내부의 투 포인터 알고리즘은 정렬된 배열에서 양 끝에서 출발하여 중앙으로 수렴하는 구조를 가지므로 O(N)입니다.
4. 투 포인터를 이동시켜서 다음 가능한 경우를 확인합니다.
5. 최종적으로 가장 가까운 합을 가지는 세 용액을 찾아 출력합니다.

 

유의해야할점은 아래와 같이 left < right 인경우까지만 입니다. 처음에 left <= right로 처리하여서 실패했었습니다.

while(left < right) { //같은경우는 고려하지 않아야합니다.

 

두번째는, 주어지는 데이터가 10억이므로, arr[] 과 answer[]는 long type으로 값을 받아야 올바르게 값을 알 수 있습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int N, M, L;
	public static long[] arr;
	
	public static long[] answer = new long[3];
    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 long[N];
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Long.parseLong(st.nextToken());
    	}
    	Arrays.sort(arr);
    	answer[0] = 1000000001;
    	answer[1] = 1000000001;
    	answer[2] = 1000000001;
    	for(int i=1; i<N-1; i++) {
    		binarySearch(i-1, i, N - 1);	
    	}
    	System.out.println(answer[0] + " "+answer[1] +  " "+answer[2]);
    	
	}
    public static void binarySearch(int selected, int start, int end) {
    	int left = start;
    	int right = end;
    	
    	while(left < right) { //같은경우는 고려하지 않아야합니다. 
    		long sum = arr[selected] + arr[left] + arr[right];
    		
    		long sumAbs = Math.abs(sum);
    		long answerAbs = Math.abs(answer[0] + answer[1] + answer[2]);
    		
    		//만약 합한 sumAbs가 
    		if(sumAbs < answerAbs) {
    			answer[0] = arr[selected];
    			answer[1] = arr[left];
    			answer[2] = arr[right];
    		}
    		
    		if(sum > 0) { //만약 0 보다 크다면, 
    			right -= 1;
    		}else if(sum < 0) {
    			left += 1;
    		}else if(sum == 0) {
    			return ;
    		}
    		
    	}
    	
    }
}

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N, M;
	public static long[] arr;
	public static long answer = 3000000001L;
	public static long[] answerArr = new long[3];
	public static StringBuilder sb = new StringBuilder();
	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 long[N];
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	Arrays.sort(arr);
    	
    	for(int i=0;i<N-2;i++) { //3가지 용액을 더하기에 1가지 용액을 확정적으로 더하면 2가지 용액을 고려하여 N-2번까지 돌린다.
    		twoPointer(i);
    	}
    	
    	Arrays.sort(answerArr);
    	System.out.println(answerArr[0]+" "+answerArr[1]+" "+answerArr[2]);
	}
	
	public static void twoPointer(int fixedIdx) {
		int start = fixedIdx + 1; //확정적으로 더할 용액보다 한개 더 큰 곳에서 시작한다.
		int end = N - 1; //마지막 용액에서 시작한다.
		
		while(start < end) {
			long value = arr[start] + arr[end] + arr[fixedIdx];
			long absValue = Math.abs(value);
			
			if(answer > absValue) {
				answer = absValue;
				answerArr[0] = arr[fixedIdx];
				answerArr[1]= arr[start];
				answerArr[2] = arr[end];
			}
			
			if(value <= 0) {
				start += 1;
			}else if(value > 0) {
				end -= 1;
			}
			
		}
	}
	
}