728x90
반응형
1655 - 가운데를 말해요
https://www.acmicpc.net/problem/1655

문제
정수 하나씩 외칠때마다 지금까지 말한 수 중에서 중간값 말해야 함
IF. 외친 수의 개수: 짝수 -> 중간에 있는 두 수 중 작은 수 말해야 함
ex. 1, 5, 2, 10, -99, 7, 5 -> 1, 1, 2, 2, 2, 2, 5
입력
첫째 줄: 외치는 정수의 개수 N (1 <= N <= 100,000, 자연수)
그 다음 N줄: 외치는 정수 (-10,000 <= 정수 <= 10,000)
출력: N줄에 거쳐 말해야 하는 수 순서대로 출력
풀이
- `maxHeap`(최대 힙): 현재까지 입력된 수 중 작은 절반(중앙값 이하)
- 큰 값 우선순위 높음(내림차순)
- `minHeap`(최소 힙): 현재까지 입력된 수 중 큰 절반(중앙값 초과)
- 작은 값 우선순위 높음(오름차순)
-> 중앙값: `maxHeap.peek()`
-> 두 힙의 크기 차이 1 이내 유지 (`maxHeap`이 항상 같거나 하나 더 많게 유지)
IF. `maxHeap` 최댓값 > `minHeap` 최솟값 = 두 힙 순서상 뒤집힘
=> swap해서 정렬 복원 (무조건 `maxHeap` 모든 값 <= `minHeap` 모든 값)
if (!minHeap.isEmpty() && maxHeap.peek() > minHeap.peek()) {
minHeap.offer(maxHeap.poll());
maxHeap.offer(minHeap.poll());
}
예시
N = 5 / 1, 5, 2, 10, -99
- 1
- maxHeap = [1] / minHeap = []
- => 중앙값: 1
- 5
- maxHeap = [5, 1] / minHeap = []
- `maxHeap.size() > minHeap.size() + 1` = 2 > 0 + 1 => True
- `minHeap.offer(maxHeap.poll())` (5)
-> maxHeap = [1] / minHeap = [5]
- `minHeap.offer(maxHeap.poll())` (5)
- `maxHeap.size() > minHeap.size() + 1` = 2 > 0 + 1 => True
- maxHeap = [1] / minHeap = [5]
- => 중앙값: 1
- maxHeap = [5, 1] / minHeap = []
- 2
- maxHeap = [2, 1] / minHeap = [5]
- => 중앙값: 2
- 10
- maxHeap = [10, 1, 2] / minHeap = [5]
- `maxHeap.peek() > minHeap.peek()` = 10 > 5 => True
- `minHeap.offer(maxHeap.poll())` (10)
-> maxHeap = [5, 1, 2] / minHeap = [10] - `maxHeap.offer(minHeap.poll())` (5)
-> maxHeap = [2, 1] / minHeap = [5, 10]
- `minHeap.offer(maxHeap.poll())` (10)
- `maxHeap.size() > minHeap.size() + 1` = 3 > 1 + 1 => True
- `minHeap.offer(maxHeap.poll())` (5)
-> maxHeap = [2, 1] / minHeap = [5, 10]
- `minHeap.offer(maxHeap.poll())` (5)
- `maxHeap.peek() > minHeap.peek()` = 10 > 5 => True
- maxHeap = [2, 1] / minHeap = [5, 10]
- => 중앙값: 2
- maxHeap = [10, 1, 2] / minHeap = [5]
- -99
- maxHeap = [2, 1, -99] / minHeap = [5, 10]
- => 중앙값: 2
=> 1 1 2 2 2
코드
import java.io.*;
import java.util.*;
// 가운데를 말해요
public class boj_1655 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
while (N-- > 0) {
int n = Integer.parseInt(br.readLine());
maxHeap.offer(n);
if (!minHeap.isEmpty() && maxHeap.peek() > minHeap.peek()) {
minHeap.offer(maxHeap.poll());
maxHeap.offer(minHeap.poll());
}
if (maxHeap.size() > minHeap.size() + 1) {
minHeap.offer(maxHeap.poll());
} else if (minHeap.size() > maxHeap.size()) {
maxHeap.offer(minHeap.poll());
}
sb.append(maxHeap.peek()).append('\n');
}
System.out.print(sb);
}
}728x90
반응형
'✏️ > BOJ' 카테고리의 다른 글
| [BOJ/Union-Find] 백준 1717 - 집합의 표현 (Java) (0) | 2025.11.09 |
|---|---|
| [BOJ/BFS] 백준 3197 - 백조의 호수 (Java) (1) | 2025.11.07 |
| [BOJ/BFS] 백준 14226 - 이모티콘 (Java) (1) | 2025.06.30 |
| [BOJ/BFS] 백준 17086 - 아기 상어 2 (Java) (0) | 2025.06.28 |
| [BOJ/BFS] 백준 2644 - 촌수계산 (Java) (1) | 2025.06.28 |