[BaekJoon] 1655번 가운데를 말해요. (Java) 문제 풀이 [Gold 2]

문제

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

1655번: 가운데를 말해요

 

어떻게 풀 것인가?

2개의 우선순위큐를 이용한다. 각각을 minHeap 그리고 maxHeap으로 선언하고 작은 값을 우선순위로 가지는 큐는 Compartor인터페이스를 사용하여 메소드를 오버라이딩한다.

 

두개의 우선순위 큐의 크기가 같은 경우는 maxHeap에 입력된 값을 추가하고, 입력한 값이 minHeap의 최솟값보다 크다면 둘을 swap한다.

 

두개의 크기가 다른 경우 minHeap에 입력된 값을 추가하며, 입력한 값이 maxHeap의 최댓값보다 작다면 둘을 swap한다.

 

maxHeap의 top에 위치한 값이 중간 값이 되게한다.

 

풀면서 놓쳤던점

2개의 우선순위큐를 사용해야 한다는 것은 아이디어를 발견하지 못했다.

사실 우선순위큐 하나에 얽메인 것이 가장 큰 문제였다.

 

 

이 문제를 통해 얻어갈 것

우선순위큐에 대한 정리

https://superohinsung.tistory.com/242

[DataStructure] Priority Queue(우선 순위 큐) feat. JAVA

 

내 코드 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

// 백준알고리즘 1655번 가운데를 말해요.
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());
        StringBuilder sb = new StringBuilder();

        PriorityQueue<Integer> minHeap = new PriorityQueue<>((o1, o2) -> o1 - o2);
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);

        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());

            if (minHeap.size() == maxHeap.size()) maxHeap.offer(num);
            else minHeap.offer(num);

            if (!minHeap.isEmpty() && !maxHeap.isEmpty())
                if (minHeap.peek() < maxHeap.peek()) {
                    int tmp = minHeap.poll();
                    minHeap.offer(maxHeap.poll());
                    maxHeap.offer(tmp);
                }

            sb.append(maxHeap.peek()).append("\n");
        }
        System.out.println(sb);
    }
}

 

참고

https://dragon-h.tistory.com/6

[백준 1655 : JAVA] 가운데를 말해요 / PriorityQueue