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

📌 문제 정보

• 번호: 1655
• 제목: 가운데를 말해요
• 난이도: Gold 2
• 분류: 자료구조, 우선순위 큐(힙)

---

💡 접근 방식

수를 하나씩 입력받을 때마다 중앙값을 출력하는 문제입니다.
최대 힙과 최소 힙 두 개를 유지하면서 중앙값을 관리합니다.

---

🔹 1단계 – 두 힙의 역할

maxHeap | minHeap
--------|--------
  3  2  |  5  7
↑
중앙값은 항상 maxHeap의 top

• maxHeap — 중앙값 이하의 수들 (최대 힙)
• minHeap — 중앙값 초과의 수들 (최소 힙)
• 중앙값은 항상 maxHeap.peek()

---

🔹 2단계 – 크기 균형 유지

if (maxHeap.size() == minHeap.size()) {
    maxHeap.add(num);
} else {
    minHeap.add(num);
}

---

🔹 3단계 – 대소 관계 정렬

if (maxHeap.peek() > minHeap.peek()) {
    maxHeap.add(minHeap.poll());
    minHeap.add(maxHeap.poll());
}

---

💻 핵심 코드

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

    if (maxHeap.size() == minHeap.size()) {
        maxHeap.add(num);
    } else {
        minHeap.add(num);
    }

    if (!maxHeap.isEmpty() && !minHeap.isEmpty() && maxHeap.peek() > minHeap.peek()) {
        maxHeap.add(minHeap.poll());
        minHeap.add(maxHeap.poll());
    }

    sb.append(maxHeap.peek()).append("\n");
}

---

⏳ 복잡도 분석

• 시간 복잡도: O(N×logN)
• 공간 복잡도: O(N)

---

📄 전체 코드

package B1655;

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

public class Main {
    static int N;

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

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());
            if (maxHeap.size() == minHeap.size()) {
                maxHeap.add(num);
            } else {
                minHeap.add(num);
            }
            if (!maxHeap.isEmpty() && !minHeap.isEmpty() && maxHeap.peek() > minHeap.peek()) {
                maxHeap.add(minHeap.poll());
                minHeap.add(maxHeap.poll());
            }
            sb.append(maxHeap.peek()).append("\n");
        }
        System.out.print(sb);
    }
}