백준 2473 '세 용액'

DoubleDeltas·2023년 9월 5일

ps 골드3 백준 이진탐색 정렬 투포인터

아이디어

코드

메모리 및 시간

리뷰

알고리즘 문제풀이

목록 보기

23/110

아이디어

숫자 하나를 고정하고 나머지 둘을 선택해 합이 최소가 되는 것을 찾자.
- 케이스가 겹치지 않도록 고정하는 수는 가장 작은 수로 고정하자.
- 즉, 고정하는 수 i에 대해 i+1~N-1 범위만 탐색한다.
특성값 순으로 정렬해놓고, 범위의 시작과 끝에서 탐색을 시작한다. (투 포인터)
합을 구해보고 그 합이 0보다 크면 숫자를 줄여야 하므로 오른쪽 포인터 q를 왼쪽으로 한 칸 옮기고, 아니라면 왼쪽 포인터 p를 한 칸 옮긴다.
i를 0부터 N-2까지 옮기며 모든 케이스를 검사해본다.

코드

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

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int N;
	static long min, ansA, ansB, ansC;
	static long[] val;
	
	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		N = Integer.parseInt(tk.nextToken());
		
		val = new long[N];
		
		tk = new StringTokenizer(rd.readLine());
		for (int i=0; i<N; i++) {
			val[i] = Long.parseLong(tk.nextToken());
		}
		
		Arrays.sort(val);

		min = Long.MAX_VALUE;
		for (int i=0; i<N-2; i++) {
			int p = i + 1;
			int q = N - 1;
			while (p < q) {
				long sum = val[i] + val[p] + val[q];
				long cur = Math.abs(sum);
				if (cur < min) {
					min = cur;
					ansA = val[i];
					ansB = val[p];
					ansC = val[q];
				}
				if (sum == 0) break;
				else if (sum > 0) q--;
				else p++;
			}
		}

		sb.append(ansA).append(' ').append(ansB).append(' ').append(ansC);
		System.out.println(sb);
	}
}