1. 문제

입력값들을 줄 단위로 받아 지금까지의 숫자들중에서 가장 중앙에 있는 값을 출력하는 문제이다.

현재까지의 숫자의 갯수가 짝수인 경우는 중간에 있는 두개의 수 중에서 더 작은 값을 출력하면 된다.

처음 이 문제를 보았을 때 그냥 ArrayList를 만들고 입력값을 받을 때마다 정렬을 할까? 라고 생각을 했지만 주어진 조건에서 N의 최대값이 100,000이기에 매번 정렬을 하게 되면 O(NNlog)으로 시간 초과가 발생하기에 다른 방법을 찾아야 했다.

Heap을 각각 최대 힙, 최소 힙을 만들면 매번 root의 값이 중앙값이 되고 시간복잡도 단축을 할 수 있기에 JAVA에서 PriorityQueue를 사용해 Heap을 구현해 보았다.

2. 문제 풀이 순서

1. 최대힙, 최소힙을 구현
2. 입력 값을 받고 만약 짝수라면 최대 힙에 offer()을 하고, 홀수라면 최소 힙에 offer()을 한다.
3. 최대 힙의 루트 노드의 값이 최소 힙의 루트 노드의 값 보다 크다면 최대 힙의 루트 노드와 최소 힙의 루트 노드의 값을 교환을 한다.
4. 최대 힙에서 element()를 통해 중앙 값을 출력

3. 코드

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

public class boj_1655_G2 {
    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<>(Collections.reverseOrder());
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        int num = Integer.parseInt(br.readLine());
        maxHeap.offer(num);
        sb.append(num).append("\n");

        // O(N * log(N/2))
        for (int i = 1; i < N; i++) {
            num = Integer.parseInt(br.readLine());

            // O(logN)
            if (maxHeap.size() == minHeap.size()) maxHeap.offer(num);
            else minHeap.offer(num);

            // O(logN)
            if (maxHeap.element() > minHeap.element()) {
                int temp = minHeap.poll();
                maxHeap.offer(temp);
                minHeap.offer(maxHeap.poll());
            }

            sb.append(maxHeap.element()).append("\n");
        }
        System.out.println(sb);
    }
}

4. PriorityQueue란?

• 일반적인 Queue와 달리 데이터의 우선 순위에 따라 요소를 추출하는 자료구조이며 내부적으로 이진 Heap 자료구조를 사용하여 구현되어 있어 시간복잡도에 대해서 매우 유리한 자료구조이다.

• PriorityQueue는 기본적으로 오름차순(낮은 숫자가 우선순위가 높음)으로 정렬되며, 이를 최소 힙(Min Heap) 방식이라고 한다.

핵심 메서드

• add() / offer() : 요소를 추가(자동으로 Heap 정렬이 됨)
• poll()/ remove() : 우선순위가 가장 높은 요소를 꺼내고 제거(자동으로 Heap 정렬이 됨)
• peek() / element() : 우선순위가 가장 높은 요소를 확인만 하고 제거는 X
  • peek()은 null을 반환
  • element()는 NoSuchElementException 발생
  • peek()이 더 유리함

PriorityQueue 메서드별 시간 복잡도

작업 유형	메서드 (예외/값 반환)	시간 복잡도	비고
삽입 (Insert)	add(e) / offer(e)	$O(\log n)$	힙 트리 재구조화 발생
삭제 (Remove)	remove() / poll()	$O(\log n)$	루트 제거 후 재구조화 발생
확인 (Examine)	element() / peek()	$O(1)$	루트 노드 즉시 반환

Heap으로 이용하는 법

기본 인스턴스 생성

//최소 힙(작은 값이 우선순위 높음)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// 최대 힙(큰 값이 우선순위 높음)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

람다식 사용

// 최대 힙(큰 값이 우선순위 높음)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

compare 메서드 구현

String 비교를 할 때는 compareTo() 사용이 중요

PriorityQueue<Student> pq = new PriorityQueue<>(new Comparator<Student>() {
    @Override
    public int compare(Student s1, Student s2) {
        // 1순위 -> 성적 내림차순(높은 값일수록 우선순위 높음)
        if (s1.score != s2.score) {
            return s2.score - s1.score;
        }

        // 2순위 -> 성적이 같은 경우 이름의 오름차순
        return s1.name.compareTo(s2.name);
    }
}

Comparator.comparing() 활용

PriorityQueue<Student> pq = new PriorityQueue<>(
    Comparator.comparingInt(Student::getScore).reversed() // 1순위: 점수 내림차순
              .thenComparing(Student::getName)            // 2순위: 이름 오름차순
              .thenComparingInt(Student::getAge)          // 3순위: 나이 오름차순
);