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

문제설명

입출력

풀이

최대힙(max-heap)과 최소힙(min-heap)을 이용한 풀이

• 힙의 크기가 같은 경우 최대힙에 삽입
• 힙의 크기가 서로 다른 경우 최소힙에 삽입
• 매 삽입마다 선택되는 중간값은 최대힙의 root 값 (poll)
• 최대힙의 root노드가 최소힙의 root노드보다 크다면 자리를 바꿈

Java Code

package com.example.boj;

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

/**
 * https://www.acmicpc.net/problem/1655
 * 가운데를 말해요
 */

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

        Queue<Integer> minH = new PriorityQueue<>((a, b) -> a-b); // min-heap
        Queue<Integer> maxH = new PriorityQueue<>((a, b) -> b-a); // max-heap

        StringBuilder sb = new StringBuilder();
        for(int i=0;i<n;i++) {
            st = new StringTokenizer(br.readLine());
            int num = Integer.parseInt(st.nextToken());
            // 힙의 크기가 서로 같은 경우 max-heap에 우선적으로 삽입
            if (minH.size() == maxH.size()) maxH.add(num);
            else minH.add(num);
            // 최대힙의 루트노드 > 최소힙의 루트노드
            if (maxH.size() > 0 && minH.size() > 0 && maxH.peek() > minH.peek()) {
                Integer tmp = maxH.poll();
                maxH.add(minH.poll());
                minH.add(tmp);
            }

            sb.append(maxH.peek() + "\n");
        }
        System.out.print(sb.toString());
    }
}