[알고리즘] Java / 백준 / 세 용액 / 2473

[알고리즘] Java / 백준 / 세 용액 / 2473

문제

문제 링크

접근 방식

1. 특성을 오름차순 정렬한다.
2. 처음 i번째 용액을 선택하고 i+1과 N-1 사이에서 두 용액을 선택하여 0에 가까운 값을 찾는다.
3. i+1과 N-1을 left, right로 두고 i, left, right 용액 합이 0보다 크면 right를 줄이고 0보다 작으면 left를 키운다.
4. left가 right를 넘지 않을 때까지 반복하며, 만약 i, left, right 용액 합이 0이면 탈출한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main_2473 {

	public static void main(String[] args) throws 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);
		
		long minDiff = Long.MAX_VALUE;
		Long answer[] = new Long[3];
		loop : for(int i=0;i<N-2;i++) {
			int l = i+1;
			int r = N-1;
			
			while(l<r) {
				Long value = arr[i] + arr[l] + arr[r];
				
				if(minDiff > Math.abs(value)) {
					answer[0] = arr[i];
					answer[1] = arr[l];
					answer[2] = arr[r];
					minDiff = Math.abs(value);
				}
				
				if(value > 0) {
					r--;
				}else if(value < 0){
					l++;
				}else break loop;
				
			}
		}
		
		Arrays.sort(answer);
		for(int i=0;i<3;i++) {
			System.out.print(answer[i] + " ");
		}
	}

}