쫑쫑이의 블로그

백준 1655 가운데를 말해요 Java [우선순위 큐] 본문

알고리즘/백준

백준 1655 가운데를 말해요 Java [우선순위 큐]

쫑쫑2 2022. 11. 20. 00:44

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

 

1655번: 가운데를 말해요

첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1

www.acmicpc.net

 

가운데 값을 기준으로 왼쪽에 최대 힙, 오른쪽에 최소 힙을 만들어주고

두 힙의 사이즈가 같거나 왼쪽이 1 더 크게 만들어서 왼쪽의 peek 값을 출력값에 넣어준다

 

import java.io.*;
import java.util.*;

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

        int Z = Integer.parseInt(br.readLine());
        left.add(Z);
        sb.append(Z).append("\n");
        for (int n = 1; n < N; n++) {
            Z = Integer.parseInt(br.readLine());
            if (left.peek() > Z) {
                left.add(Z);
                if (left.size() > right.size() + 1) {
                    right.add(left.poll());
                }
            } else {
                right.add(Z);
                if (right.size() > left.size()) {
                    left.add(right.poll());
                }
            }
            sb.append(left.peek()).append("\n");
        }
        sb.setLength(sb.length() - 1);
        System.out.println(sb);
    }
}