[Java] BOJ2473_세 용액

www.acmicpc.net/problem/2473

2473번: 세 용액

---

두 용액 문제에서 포인터가 하나 더 추가된 문제이다.

 

방식은 두 용액과 유사하여 왼쪽과 오른쪽을 포인터로 두고 그 가운데 값 중 합을 가장 0과 가깝게 만드는 값을 찾아 최솟값 비교를 해주었다. 하지만 이 코드로 통과하지 못하여 다른 방식으로 접근하였다.

 

왼쪽 값은 고정되어 있고 왼쪽 값을 기준으로 가운데 값고 오른쪽 값을 두 포인터로 잡아 탐색하는 것이다.

 

위 두 방식 모두 전 범위를 탐색한다고 생각하는데 왜 첫번째 방식이 안 되는지 아직 모르겠다.

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		long[] arr = new long[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Long.parseLong(st.nextToken());
		}
		Arrays.sort(arr);
		int left = 0;
		int right = N-1;
		int center = left+1;
		long resL = 0, resR = 0, resC = 0;
		long min = Long.MAX_VALUE;
        
        //왼쪽과 오른쪽을 두 포인터로 두고 그 가운데를 탐색
//		while(true) {
//			if(right-left == 1) break;
//			center = left+1;
//			long sum = arr[left] + arr[right];
//			for (int i = left+2; i < right; i++) {
//				if(Math.abs(sum + arr[center]) > Math.abs(sum + arr[i])) {
//					center = i;
//				}
//			}
//			sum += arr[center];
//			if(Math.abs(sum) <= min) {
//				min = Math.abs(sum);
//				resL = arr[left];
//				resR = arr[right];
//				resC = arr[center];
//			}
//			if(sum < 0) {
//				left++;
//			} else {
//				right--;
//			}
//			
//		}

		//왼쪽이 고정되어 있고 가운데와 오른쪽을 두 포인터
		for(int i=0; i < N-1; i++) {
			int j = i+1;
			int k = N-1;
			while(true) {
				if(j==k) break;
				long sum = arr[i] + arr[j] + arr[k];
				if(Math.abs(sum) <= min) {
					resL = arr[i];
					resC = arr[j];
					resR = arr[k];
					min = Math.abs(sum);
				}
				if(sum < 0) {
					j++;
				}else {
					k--;
				}
			}
		}
		System.out.println(resL + " " + resC + " " + resR);
	}

}