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

문제

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

1655번: 가운데를 말해요

 

 

풀이 과정

입력된 수를 최대힙과 최소힙에 나눠 저장해서 중간 값이 최대힙의 top에 있도록 했다. 최대힙은 값을 넣을 때, 음수로 넣어서 최소힙을 활용한 최대힙을 만들었다.

최대힙의 크기 >= 최소힙의 크기로 밸런스를 맞춰서 최대힙.peek()를 출력해주면 된다.

1. mid값보다 크면, 최소힙에 삽입

     1-1. 최소힙의 크기 > 최대힙의 크기면, 최대힙.offer(최소힙.poll())

2. mid값보다 작거나 같으면, 최대힙에 삽입

     2-1. 최대힙의 크기 > 최소힙의 크기 + 1이면, 최소힙.offer(최대힙.poll())

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>();
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        int mid = Integer.parseInt(br.readLine());
        maxHeap.add(-mid);
        sb.append(mid).append("\n");
        for(int i=2; i<=N; i++){
            int num = Integer.parseInt(br.readLine());
            if(mid < num){
                minHeap.offer(num);
                if(minHeap.size() > maxHeap.size()){
                    maxHeap.offer(-minHeap.poll());
                }
            }
            else{
                maxHeap.offer(-num);
                if(maxHeap.size() > minHeap.size()+1){
                    minHeap.offer(-maxHeap.poll());
                }
            }

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

 

 

결과