b.2696 중앙값 구하기

 

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

 

 

 

📌 자바(Java)로 푸는 중앙값 구하기 - 백준 2696 🔢

 

---

🔎 문제 개요

 

백준 2696번 - 중앙값 구하기 문제는

여러 개의 수열이 주어졌을 때,

각 수열마다 홀수 번째 수를 입력받을 때마다의 중앙값을 구하는 문제입니다.

 

• 입력 수열의 개수: T
• 각 수열은 최대 10씩 끊어져 입력
• 홀수 번째 수가 들어올 때마다 중앙값 출력

 

---

💡 예제 입력

1
9
1 2 3 4 5 6 7 8 9

 

💡 예제 출력

5
1 2 3 4 5

 

 

---

🛠 알고리즘 접근 방식

 

이 문제는 대표적인 중앙값(Median) 유지 문제로,

**최대 힙(왼쪽 절반) + 최소 힙(오른쪽 절반)**을 사용하여 중앙값을 효율적으로 관리합니다.

 

 

✏️ 핵심 아이디어

 

• left: 최대 힙, 중앙값보다 작은 값 저장
• right: 최소 힙, 중앙값보다 큰 값 저장
• 짝수 개 → left와 right 균형 유지,
• 홀수 개 → left가 항상 더 많도록 유지
• 홀수 번째 수가 들어오면 left.peek()가 중앙값

 

---

🔹 Java 코드 해설

Queue<Integer> left = new PriorityQueue<>(Collections.reverseOrder()); // max heap
Queue<Integer> right = new PriorityQueue<>(); // min heap

✔ left: 중앙값 이하 숫자

✔ right: 중앙값 초과 숫자

 

if(left.isEmpty() || left.peek() < num){
    left.offer(num);
} else {
    right.offer(num);
}

✔ 처음엔 left에 넣고,

✔ 정렬을 유지하기 위해 두 힙의 사이즈를 맞춰줌

 

if (left.size() > right.size() + 1) {
    right.offer(left.poll());
} else if (right.size() > left.size()) {
    left.offer(right.poll());
}

✔ 힙의 크기를 **left ≥ right**가 되도록 유지

 

if(i % 2 == 0){
    answer++;
    sb.append(left.peek()).append(" ");
}

✔ 홀수 번째 수가 들어왔을 때마다 left.peek() 출력

✔ 이는 현재 입력된 수열의 중앙값

 

 

🔍 입출력 처리

for(int i = 0; i < N; i += 10){
    input.append(br.readLine()).append(" ");
}

✔ 백준에서 한 줄에 최대 10개의 숫자만 주어지므로,

✔ 여러 줄을 받아서 하나의 스트링으로 처리

 

---

🏆 정리

✅ 핵심 포인트

 

✔ 중앙값 문제는 항상 **“두 개의 힙”**을 생각

✔ **왼쪽(최대 힙)**은 중앙값 이하

✔ **오른쪽(최소 힙)**은 중앙값 초과

✔ left.peek()가 항상 중앙값이 되도록 유지