BOJ - 2473 ) 세용액

 

---

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

2473번: 세 용액

 

---

세용액의 합이 0 이 가까운 것은 고르기 위해서, 정렬후 앞쪽부터 O(n)만큼 순차탐색을 하도록하자.

 

세개의 포인터를 사용해야하기때문에, 하나는 고정시키고 두개를돌려주자

 

5000^2으로 충분하다

 

 

---

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

public class 세용액 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		long arr[] = new long[n];
		long answer = Long.MAX_VALUE ;
		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < n ; i ++) { arr[i] = Long.parseLong(st.nextToken());}
		Arrays.sort(arr);
		int s=0,m=0,e=n-1;
		int i1=0,i2=0,i3=0;
		top:
		for( s=0 ; s < n ; s++) {
			long now = arr[s];
			m = s+1;
			e = n-1;
			if(m >=n && e <=m) continue;
			for( ; m < e ;) {
				long snumber = arr[m];
				long enumber = arr[e];
				long sum = now+ snumber + enumber;
				if(Math.abs(sum) < Math.abs(answer)) {
					answer = sum;
					i1=s;i2=m;i3=e;
				}
				if(sum >0)e--;
				else if(sum==0) break top;
				else {m++;	}
			}
		}System.out.print(arr[i1] +" "+arr[i2] + " "+arr[i3]);
	}

}

---