[백준 2470] 두 용액 Java 풀이

2470번: 두 용액

 

접근

n이 최대 100,000이므로 이중 for 문으로 0에 가장 가까운 용액을 만들어내는 두 용액을 찾으면 최악의 경우 시간 복잡도가 O(n^2)이 될 것으로 예상됩니다. 따라서 투 포인터를 이용한다면 시간 복잡도를 O(n)으로 줄일 수 있습니다.

 

코드

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());
		int[] arr = new int[n];

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

		// 1. 배열 arr를 오름차순으로 정렬한다.
		Arrays.sort(arr);

		// 2. 투 포인터를 이용하여 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는다.
		int a = 0, b = 0;
		int i = 0, j = n - 1;
		int min = 2_000_000_000;
		while (i < j) {
			int sum = arr[i] + arr[j];

			if (Math.abs(sum) < min) {
				min = Math.abs(sum);
				a = arr[i];
				b = arr[j];
			}

			if (sum <= 0) {
				i++;
			} else {
				j--;
			}
		}

		// 결과 출력
		System.out.println(a + " " + b);
	}
}