[JAVA][백준 2473][투 포인터] 세 용액 - 컴도리돌이

반응형

2473번: 세 용액

---

세 용액의 합이 0과 가장 근사한 값을 찾아야 한다.

용액의 수가 5000 이하이기 때문에

최악일 경우 5000 * 2500 = 7500000의 연산을 계산하기 때문에 

시간 복잡도에 대한 걱정 없이 해결할 수 있었다.

 

기준점 i번째의 값부터 n-1의 값까지 j번째와 k번째의 합들 중에서 최솟값을 구했다.

여기서 j번째는 i+1, k번째는 n-1번째로 설정하여

투 포인터 알고리즘으로 해결하였다.

i, j, k번째의 합이 비교대상 comp과 비교하여 최솟값과 인덱스 값을 업데이트해주었다.

---

	package 투포인터;
	import java.util.*;
	public class boj2473 {
	static Scanner sc = new Scanner(System.in);
	static int n;
	static Long [] arr;
	static void input(){
	n = sc.nextInt();
	arr = new Long [n];
	for(int i=0; i < n ; i++){
	arr[i] = sc.nextLong();
	}
	Arrays.sort(arr);
	}
	static void solution(){
	Long comp = Long.MAX_VALUE;
	int a=0,b=0,c=0;
	for(int i=0; i < n ; i ++){
	int j = i+1, k = n-1;
	while (j < k){
	Long sum = arr[i] + arr[j] + arr[k];
	if(Math.abs(sum) < comp ){
	a= i ; b= j ; c = k; comp = Math.abs(sum);
	}
	if(sum < 0) j ++;
	else k --;
	}
	}
	System.out.printf("%d %d %d",arr[a],arr[b],arr[c]);
	}
	public static void main(String[] args) throws Exception {
	input();
	solution();
	}
	}

view raw boj2473.java hosted with ❤ by GitHub