[백준 2473번] 세 용액

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

 

문제 유형

• 정렬
• 투 포인터
• 이분 탐색

문제 난이도

• Gold 3

문제 분석

각 용액에 대한 특성값이 나오고, 세 개의 용액을 선택해서 특성값을 더했을 때, 특성값이 0에 가까운 용액을 구하는 문제이다.

우선 이런 문제의 경우, 각 정렬들을 오름차순으로 정렬하고, 이분 탐색이나 투 포인터를 해야 한다.
내가 이 문제를 풀 때, 오래 걸리고 실수한 부분은 투 포인터라는 관점을 생각했지만, 완전 탐색의 논리 구조와 혼동이 왔다.

각각 시작점과 종료 지점을 선택하고, 한 칸씩 앞과 뒤로 당기면 결국 시간 복잡도는 O(N)이 되는데, 혼동이 생겼다.

따라서 하나의 용액을 target으로 잡아주고, 나머지 두 용액에 대해 target 이후의 인덱스에 대해서 투 포인터를 적용하면 
시간 복잡도 = O(N) * O(N) = O(N^2)이 되므로 시간초과가 나지 않는다. (N <= 5,000)
=> 순차적으로 하나의 용액을 선택 : O(N)
=> 투 포인터를 통해 나머지 두 용액을 선택하고 세 용액의 특성값을 더해서 절댓값을 통해 0과 가까워지는 용액에 대하여 배열에 값을 저장한다.

해당 풀이 방법만 생각한다면 어렵지 않게 풀 수 있다.

 

전체 코드

package _250715;

import java.util.*;
import java.io.*;
/**
 *packageName    : _250715
 * fileName       : BOJ_G3_2473_세용액
 * author         : moongi
 * date           : 7/15/25
 * description    :
 */
public class BOJ_G3_2473_세용액 {
	static int N;
	static long[] arr, res;
	static Long ans;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		N = Integer.parseInt(br.readLine());
		arr = new long[N];
		ans = Long.MAX_VALUE;
		res = new long[3];

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(arr);

		for (int i = 0; i < N - 2; i++) {
			solve(i);
		}

		Arrays.sort(res);

		for (int i = 0; i < 3; i++) {
			sb.append(res[i]).append(" ");
		}

		System.out.println(sb);
	}

	static void solve(int target) {

		int start = target + 1;
		int end = N - 1;

		while (start < end) {

			long sum = arr[start] + arr[end] + arr[target];
			long absSum = Math.abs(sum);

			if (absSum < ans) {
				ans = absSum;

				res[0] = arr[start];
				res[1] = arr[end];
				res[2] = arr[target];
			}

			if (sum >= 0) {
				end--;
			} else {
				start++;
			}
		}
	}
}