b1655. 가운데를 말해요

 

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

 

 

 

🎤 자바로 푸는 가운데를 말해요 문제 풀이

 

---

 

📌 문제 개요

 

• 숫자가 하나씩 주어질 때마다, 지금까지 입력된 수들 중 가운데 수를 출력하는 문제입니다.
• 단, 입력은 실시간으로 주어지며, 모든 수는 정수입니다.

 

---

 

💡 예제 입력

7
1
5
2
10
-99
7
5

 

예제 출력

1  
1  
2  
2  
2  
2  
5

 

---

 

🛠 알고리즘 접근 방식

 

이 문제는 중간값(Median)을 실시간으로 관리하는 것이 핵심입니다.

 

 

✅ 핵심 아이디어: 두 개의 힙(PriorityQueue)

 

• 최대 힙 (왼쪽): 중간값보다 작은 수들을 저장
• 최소 힙 (오른쪽): 중간값보다 큰 수들을 저장
• 중간값은 항상 최대 힙의 top에 위치하도록 관리

 

힙의 크기를 조정하면서 항상 최대 힙 ≥ 최소 힙 유지

 

---

 

🧾 코드 해설

PriorityQueue<Integer> pq = new PriorityQueue<>(); // 최소 힙 (오른쪽)
PriorityQueue<Integer> subpq = new PriorityQueue<>(Collections.reverseOrder()); // 최대 힙 (왼쪽)

int num = Integer.parseInt(br.readLine());
pq.add(num);

// 삽입 직후, 두 힙이 순서를 어기면 swap
if((!pq.isEmpty() && !subpq.isEmpty()) && pq.peek() < subpq.peek()){
    pq.add(subpq.remove());
    subpq.add(pq.poll());
}

// 균형 맞추기
if(pq.size() > subpq.size() + 2)
    subpq.add(pq.poll());
else if(pq.size() == subpq.size())
    pq.add(subpq.poll());

// 항상 가운데는 최소힙의 top
sb.append(pq.peek()).append("\n");

 

---

 

✅ 핵심 포인트 요약

포인트	설명
중간값 유지	최대 힙 + 최소 힙 사용
삽입	숫자를 적절한 힙에 추가
정렬	힙의 top 비교 후 교환
균형 유지	힙의 크기를 조정하여 중간값이 왼쪽(최대 힙)에 가깝게 유지

 

---

 

🎯 결론: 실시간 중간값은 두 힙으로 해결하자

 

이 문제는 단순한 정렬 문제가 아닌, 스트리밍 데이터에서의 중간값 관리 문제입니다.