[백준/JAVA] 2473_세 용액

백준🔗

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

2473번: 세 용액

 

문제

 

간단 풀이

이전에 풀었던 문제 "2467 용액"과 같은 원리이다.

다만, 현재 문제에서는 특성값들이 오름차순 or 내림차순으로 정렬되어 있다는 조건이 없기 때문에 특성값을 입력받은 후 정렬 과정을 한 번 거쳤다.

 

그리고 용액이 3개로 늘어났기 때문에 1, 2번째 용액을 고정시켜두고, 3번째 용액을 찾을 때 이분 탐색을 수행했다.  이분 탐색의 시간복잡도는 O(logn)

(이전 코드를 그대로 가져오다가 수정을 잘못해서 몇 번 틀렸습니다를 봐야 했다..)

 

특성값의 범위는 동일하게 최대 10억까지인데 용액이 3개로 늘어났으니 합이 30억이 되면 int형의 범위를 벗어나기 때문에 long형으로 수정해줬다.

 

코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		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[] res = new long[3];
		long sum = Long.MAX_VALUE;
		here: for (int j = 0; j < N - 2; j++) {
			for (int i = j + 1; i < N - 1; i++) {
				long tmp = arr[i] + arr[j];
				int start = i + 1;
				int end = N - 1;
				int mid = 0;
				while (start <= end) {
					mid = (start + end) / 2;
					if (tmp + arr[mid] < 0) {
						start = mid + 1;
					} else if (tmp + arr[mid] > 0) {
						end = mid - 1;
					} else {
						res[0] = arr[j];
						res[1] = arr[i];
						res[2] = arr[mid];
						break here;
					}
					if (Math.abs(tmp + arr[mid]) < sum) {
						sum = Math.abs(tmp + arr[mid]);
						res[0] = arr[j];
						res[1] = arr[i];
						res[2] = arr[mid];
					}
				}
			}
		}
		System.out.println(res[0] + " " + res[1] + " " + res[2]);
	}
}

 

 

참고 자료

2023.06.07 - [알고리즘/백준] - [백준/JAVA] 2467_용액