문제 - 1655

문제접근

처음에는 값을 넣을 때마다 정렬을 한다음 index를 이용하여 배열의 크기가 홀수개 일때에는 size/2의 값을 출력하고 짝수개일 경우에는 size/2 -1의 값을 출력을 했지만 시간초과가 떴다.
그래서 우선순위큐를 이용하고자 했다.
일단 단순구현으로는 시간초과로 통과를 하지 못하므로 최대힙과 최소힙을 이용하여 값의 중간값들로만 계산을 했다.
1. 최대힙과 최소힙의 크기가 같은 경우에는 최대힙부터 값을 채운다.
2. 최대힙.peek() > 최소힙.peek()인 경우에는 두개의 값을 바꾼다.
3. 최대힙의 값을 저장한다.

N개만큼 최대힙의 값을 출력을 하면 시간초과가 나므로 StringBuilder를 이용하여 한번에 출력해준다.

소스코드

import java.util.*;
import java.io.*;
public class Main {

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

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

        PriorityQueue<Integer> minPq= new PriorityQueue<>();
        PriorityQueue<Integer> maxPq = new PriorityQueue<>(Comparator.reverseOrder());
        StringBuilder sb = new StringBuilder();

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

            //크기가 같은 경우에는 최대힙으로
            if(minPq.size() == maxPq.size())
            {
                maxPq.add(number);
            }else {
                minPq.add(number);
            }

            if(!minPq.isEmpty() && maxPq.peek() > minPq.peek())
            {
                minPq.add(maxPq.poll());
                maxPq.add(minPq.poll());
            }

            sb.append(maxPq.peek()).append("\n");
        }
        System.out.println(sb.toString());
    }


}