[백준] 2470번 : 두 용액 - 자바[Java]

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

2470번: 두 용액

 

풀이

2 <= N <= 100,000 이므로 O(n)의 시간복잡도로 문제를 풀어야 한다.

두 용액 값을 더한  값 중 0에 가까운 값을 구해야 하므로, 용액 값을 정렬한 다음 투포인터 알고리즘을 사용하여 O(n)의 시간복잡도로 문제를 풀었다.

 

로직

1. 특성용액을 정렬한다.

2. 투포인터 알고리즘을 사용한다. 초기값: l = 0, r = n-1

- 두 용액의 특성값의 절대값을 구해서 min값과 ans1, ans2 값을 업데이트한다.

- 두 용액의 특성값이 0보다 작으면 l++, 0보다 크면 r--를 한다. 0이면 반복문을 탈출한다.

코드

import java.io.*;
import java.util.*;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		//StringBuilder sb = new StringBuilder();
		
		int n = Integer.parseInt(br.readLine());
		ArrayList<Integer> list = new ArrayList<>();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			list.add(Integer.parseInt(st.nextToken()));
		}
		
		Collections.sort(list);
		
		int l = 0, r = n - 1; // 투 포인터
		int ans1 = 0, ans2 = 0; // 두 용액
		boolean flag = false; // 특성값이 0이 되는 경우 true
		int min = Integer.MAX_VALUE; // 두 용액의 특성값의 최솟값
		
		while (l < r) {
			int sum = 0;
			sum += list.get(l);
			sum += list.get(r);
			if (min > Math.abs(sum)) {
				min = Math.abs(sum);
				ans1 = list.get(l);
				ans2 = list.get(r);
			}
			
			if (sum < 0) {
				l++;
			}
			else if (sum > 0) {
				r--;
			}
			else {
				flag = true;
				bw.write(list.get(l) + " " + list.get(r));
				break;
			}
		}
		
		if (!flag) {
			bw.write(ans1 + " " + ans2);
		}
		
		bw.flush();
		br.close();
		bw.close();
	}
}