[Java] 백준 - 1655번: 가운데를 말해요

5월 21일(화) - 자료 구조(1655번)

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

---

최초 생각 정리

---

문제점

---

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

        int N = Integer.parseInt(br.readLine());
        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() + "\n");
        }

        System.out.println(sb);
    }
}

---