[ 알고리즘 ] 코딩 - 백준 2470 - 두 용액.java

---

문제 링크

www.acmicpc.net/problem/2470

2470번: 두 용액

---

문제 개요

백준 - BOJ - 2470번 - (자바) 두용액 - 투 포인터

입력값 : 알칼리 = -1,000,000,000, 산성 = 1,000,000,000

두 용액의 합이 0에 가까운 것을 찾아내는 문제

모든 입력이 알칼리일 수도 있고, 산성일 수도 있다.

N : 2이상 100000 이하

입력 예시

출력 예시

---

로직

Step 01. 모든 용액의 값을 배열에 입력 받는다

Step 02. 배열을 오름차순 정렬한다

Step 03. 가장 왼쪽 인덱스 left하나, 가장 오른쪽 인덱스 right하나를 둔다

Step 04. left와 right의 인덱스의 원소를 더하고(sum), 그 값의 절대값을 취한다(cur_diff).

Step 05. 절대값을 비교하고 차이가 더 작은 경우 저장한다

Step 06. sum 값이 0보다 크다면 right를 1 줄이고 0보다 작다면 left를 1 늘린다

Step 07. 모든 값을 탐색하고 마지막에 저장되어있는 left와 right 인덱스의 원소가 정답

---

코드

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[] solutions = new int[N];

		StringTokenizer stt = new StringTokenizer(br.readLine());

		for (int i = 0; i < N; i++) {
			int next = Integer.parseInt(stt.nextToken());
			solutions[i] = next;
		}

		Arrays.sort(solutions); // 오름차순 정렬

		int left = 0; // 가장 왼쪽
		int right = N - 1; // 가장 오른쪽
		int diff = Integer.MAX_VALUE;
		int left_el = 0;
		int right_el = 0;

		while (left < right) {
			// 두 용액의 합
			int sum = solutions[left] + solutions[right];

			// 차이
			int cur_diff = Math.abs(sum);

			if (cur_diff < diff) { // 차이가 더 작은 경우
				// 값 저장
				diff = cur_diff;
				left_el = solutions[left];
				right_el = solutions[right];
				if (diff == 0)
					break;
			}

			if (sum > 0) { // 0 보다 크면 오른쪽 요소 한칸 앞으로 이동
				right--;
			} else { // 0보다 작으면 왼쪽 요소 한칸 앞으로 이동
				left++;
			}
		}
		System.out.println(left_el + " " + right_el);
	}
}