[백준] 1655 가운데를 말해요 - Data Structure / Java

• 문제 링크

1655번: 가운데를 말해요

 

• 풀이 과정

최대값을 우선으로 반환하는 최대힙과 최소값을 우선으로 반환하는 최소힙을 활용한다.

 

두 힙의 크기를 비교하여 크기가 같을 때는 최대힙에,

다를 때는 최소힙에 입력받은 정수를 번갈아 가며 저장한다.

 

두 힙의 우선순위 값을 비교하여 최대힙의 값이 더 크다면 비교한 두 값을 교체한다.

 

이렇게 최대힙의 값이 최소힙의 값보다 항상 작도록 유지하면

각 시점마다 최대힙의 우선순위 값이 제시한 조건의 중간값이므로, 이를 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;

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));

        int n = Integer.parseInt(br.readLine());

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

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

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

            if (!minHeap.isEmpty() && maxHeap.peek() > minHeap.peek()) {
                minHeap.offer(maxHeap.poll());
                maxHeap.offer(minHeap.poll());
            }

            bw.write(maxHeap.peek() + "\n");
        }

        bw.flush();
    }

}