백준 2467번 용액 [Java]

문제

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

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt((n) -> Math.abs(n)));
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			pq.add(Integer.parseInt(st.nextToken()));
		}
		long answer1 = 0, answer2 = 0;
		long min = Long.MAX_VALUE;
		for(int i = 0; i < N - 1; i++) {
			long a = pq.poll();
			long sum = a + pq.peek();
			if(sum == 0) {
				answer1 = a;
				answer2 = pq.poll();
				break;
			}
			else {
				if(Math.abs(sum) < min) {
					answer1 = a;
					answer2 = pq.peek();
					min = Math.abs(sum);
				}
			}
		}
		StringBuilder sb = new StringBuilder()
				.append((answer1 < answer2) ? answer1 : answer2)
				.append(" ")
				.append((answer1 > answer2) ? answer1 : answer2);
		System.out.println(sb);
		
	}

}

 

접근방법

처음에 들었던 생각은 어차피 정렬된 순으로 주어지니 가장 작은 음수와 가장 큰 양수를 더하면 되지 않을까? 싶었지만

-1000 2 1 100 이런게 들어오면 답이 틀리게 돼서 안되는 방법 같았다.

조합으로 모든 경우의 수를 고려하면 입력N이 10만까지 되기 때문에 터져버린다.

그래서 입력값을 절대값 순으로 다시 정렬하고 앞에서 부터 2개씩 확인하면서 합의 절대값의 min을 찾았다.

만약 탐색 중 합이 0이되는 경우가 나온다면 0보다 0에 가까운 수는 없기 때문에 탐색 종료

priority queue를 사용해서 정렬해주었기 때문에 pq의 시간복잡도는 O(log N)

앞에서부터 탐색하는 것의 시간 복잡도는 O(N) 따라서 총 시간은 O(N log N)이므로 시간내에도 들어올거라고 판단했다.

 

pq에서 PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt((n) -> Math.abs(n))); 이 부분을 자동완성으로 적고 생각해보니

보통 코테에서는 IDE사용 금지니까 좀 외워야겠다고 생각했다.. 프로그래머스나 소프티어 문제였다면 아마 백퍼 못 적었을거 같다.

백준으로만 풀다보면 이런 자동완성에 의지하는게 문제인듯

 

내가 푼 방법은 정렬과 그리디적인 접근 방법이었는데

풀고나서 해당 문제의 알고리즘 분류를 보니까 투포인터와 이분탐색이었다. 

그래서 어떻게 푸는지 찾아보니 내가 처음 생각했던 방법대로 가장 작은 수와 가장 큰 수에 두 포인터를 두고 시작해서 탐색하며 0에 가깝게 포인터를 이동시키는 방법인거 같다. 혹시 N의 범위가 더 컸더라면 내가 풀었던 방법은 안 먹힐거 같기 때문에 이 방법도 기억해둬야겠다.