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

1. 최대/최소 우선순위 큐의 크기가 같으면 최대 큐에 삽입하고 같지 않다면 최소 큐에 삽입함.
2. 최대/최소 우선순위 큐가 비어있지 않고, 최대 큐의 루트값이 최소 큐의 루트값보다 크다면 두 값의 자리를 바꿔줌.
3. 최대 우선순위 큐의 루트값을 출력함

1. 리스트 사용
시간초과

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

        List<Integer> input = new ArrayList<>();

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            input.add(Integer.valueOf(br.readLine()));
            input.sort(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    if (o1 > o2) return 1;
                    else if (o1 < o2) return -1;
                    else return 0;
                }
            });

            int idx = input.size()/2;
            if (i % 2 == 0 ) {
                sb.append(input.get(idx) + "\n");
            }
            else {
                sb.append(input.get(idx-1) + "\n");
            }
        }
        System.out.println(sb);
    }
}

2. 최대/최소 힙 사용

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

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            int input = Integer.parseInt(br.readLine());

            if (maxHeap.size() == minHeap.size())
                maxHeap.add(input);
            else
                minHeap.add(input);

            if (!maxHeap.isEmpty() && !minHeap.isEmpty() && maxHeap.peek() > minHeap.peek()) {
                maxHeap.add(minHeap.poll());
                minHeap.add(maxHeap.poll());
            }
            sb.append(maxHeap.peek() + "\n");
        }
        System.out.println(sb);
    }
}