백준 2467 - 용액 (이분탐색, 투포인터)

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

👆👆 더보기를 누르시면 문제 링크를 확인하실 수 있습니다.

문제 요약

- 산성 용액과 알칼리성 용액의 특성값이 정렬된 순서로 주어진다.

- 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가까운 용액을 만들어 내는 두 용액을 출력하라.

* 혼합한 용액의 특성값: 혼합에 사용된 각 용액의 특성값의 합 

 

---

제한 조건

- 전체 용액의 수 (2≤ N ≤ 100,000)

(100,000 가지 중 2가지 경우의 수를 찾으면 경우의 수가 상당히 많아져 1초만에 문제를 풀기에 무리가 있다.)

- 용액의 특성 값 (-1,000,000,000 ≤ M ≤ 1,000,000,000) (Long 타입)

---

아이디어 

- Two pointer (왼쪽 인덱스, 오른쪽 인덱스)

- 왼쪽 인덱스가 가리키는 특성 값과 오른쪽 인덱스가 가리키는 특성 값의 합이 0보다 작으면 왼쪽 인덱스 값 증가

∵ (왼쪽 인덱스가 가리키는 값 + 오른쪽 인덱스가 가리키는 값)의 절댓값이 0에 가까워 져야하기 때문에

- 특성 값의 합이 0보다 크면 오른쪽 인덱스의 값이 더 크므로 오른쪽 인덱스 값 감소

- 두 특성 값의 합 절댓값이 0에 가장 가까운 두 수 출력

∵ 특성 값의 합에 절댓값을 취하는 이유는 음의 값과 양의 값에 상관 없이 0에 가까이 위치하는 수를 찾기 위해서다.

---

코드 (Java)

import java.util.Scanner;

public class BS_boj_2467 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		long[] items = new long[N];

		for (int i = 0; i < N; i++) {
			items[i] = sc.nextLong();
		}

		// 1. 정렬 (필요 XX) - 이미 오름차순으로 입력이 주어진다.

		int left = 0; // 배열 왼쪽 끝 index
		int right = N - 1; // 배열 오른쪽 끝 index

		long ans1 = 0, ans2 = 0; // 출력할 두 수 

		long min = Integer.MAX_VALUE; // 0에 가까운 값 (절댓값)

		// 2. 이분탐색 
		// left가 커지고 right가 줄어들다보면 left == right가 같아지는 순간이 온다.
		// left와 right가 같아질 경우 같은 수를 가리키는 것을 의미하기 때문에
		// left <= right 가 아닌, left < right 가 되어야 한다.
		while (left < right) {
			long sum = items[left] + items[right]; // 두 인덱스의 합

			if (min > Math.abs(sum)) { 
				// 절댓값을 이용하지 않으면, min은 -가 될 수 있다.
				// -든 +든 0에 가까운 값을 찾는 것이므로 절댓값을 취해준다. 
				min = Math.abs(sum);
				ans1 = items[left];
				ans2 = items[right];
			}

			// sum이 0보다 작았다는 것은 왼쪽 값이 오른쪽 값보다 절댓값을 취했을 때 크다는 것을 의미한다.
			// 왼쪽을 증가시켜 sum의 수를 줄인다. 
			if (sum < 0)
				left++;
			else
				right--;
			// sum이 0보다 크다는 것은 오른쪽 값이 왼쪽 값보다 절댓값을 취했을 때 크다는 것을 의미한다.
			// 오른쪽을 감소시켜 sum의 수를 줄인다. (sum의 수를 줄여야 0에 가까운 값을 찾을 수 있다.)
		}

		System.out.println(ans1 + " " + ans2);
	}
}