[백준] 🥇 2470 두 용액

📌 난이도

🥇 Gold 5

📌 문제

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

📌 풀이

일단 이 문제를 보고 든 생각은 정렬을 하기는 해야하는데, Arrays.Sort를 사용하면 o(n^2) = 10,000,000,000 의 시간복잡도가 생긴다.
따라서, o(nlog(n))의 시간복잡도인 우선순위 큐를 통해서 정렬을 하였다.

하지만 우선순위 큐를 사용하면 가장 큰 값은 알 수 있지만, 가장 작은 값은 알 수가 없다.
그래서 오름차순 우선순위 큐와, 내림차순 우선순위 큐 두개를 만들어서, 서로 값이 같을 때까지 비교를 해주었다.
다음은 그 코드이다.

📌 Code

package BOJ.TwoPointer;

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

public class N2470 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> ascend = new PriorityQueue<>();
        PriorityQueue<Integer> descend = new PriorityQueue<>(Collections.reverseOrder());
        st = new StringTokenizer(br.readLine());
        int num;

        for (int i = 0; i < N; i++) {
            num = Integer.parseInt(st.nextToken());
            ascend.add(num);
            descend.add(num);
        }

        int max = descend.remove();
        int min = ascend.remove();
        int[] closeZero = {max, min};

        while (max != min) {
            if (max + min > 0) {
                max = descend.remove();
            } else {
                min = ascend.remove();
            }
            if (max == min) {
                break;
            }
            if (Math.abs(closeZero[0] + closeZero[1]) > Math.abs(max + min)) {
                closeZero = new int[]{max, min};
            }
        }
        System.out.println(closeZero[1] + " " + closeZero[0]);
    }
}

package (이름); 를 때고, class 이름을 Main으로 변경하면 된다.

---

개인 공부 기록용 블로그입니다.
틀리거나 오류가 있을 경우 제보해주시면 감사하겠습니다.😁