6074 : 중간값 스트림
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
중간값 스트림 (Running Median)
정수가 하나씩 입력될 때마다, 현재까지 입력된 수들의 중간값(Median)을 실시간으로 출력하시오.
정의: 짝수 개일 경우 더 작은 값을 중간값으로 정의합니다.
핵심 아이디어: 두 힙 활용
- 최대힙 lo: 중간값 이하의 수들 (루트 = 중간값 후보)
- 최소힙 hi: 중간값 초과의 수들
- 항상 len(lo) == len(hi) 또는 len(lo) == len(hi)+1 유지
시간복잡도: $O(N \log N)$
[제약 조건]
• 스트림 원소 수 $N$: $1 \le N \le 100{,}000$ (정수)
• 각 원소: $-10^9 \le x \le 10^9$ (정수)
정수가 하나씩 입력될 때마다, 현재까지 입력된 수들의 중간값(Median)을 실시간으로 출력하시오.
정의: 짝수 개일 경우 더 작은 값을 중간값으로 정의합니다.
핵심 아이디어: 두 힙 활용
- 최대힙 lo: 중간값 이하의 수들 (루트 = 중간값 후보)
- 최소힙 hi: 중간값 초과의 수들
- 항상 len(lo) == len(hi) 또는 len(lo) == len(hi)+1 유지
시간복잡도: $O(N \log N)$
[제약 조건]
• 스트림 원소 수 $N$: $1 \le N \le 100{,}000$ (정수)
• 각 원소: $-10^9 \le x \le 10^9$ (정수)
입력 설명
첫째 줄에 정수의 개수 N (1 ≤ N ≤ 50,000)이 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 정수가 하나씩 입력됩니다.
둘째 줄부터 N개의 줄에 걸쳐 정수가 하나씩 입력됩니다.
출력 설명
정수가 입력될 때마다 현재까지의 중간값을 한 줄에 하나씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
5
3
8
1
6
출력 예시
COPY
복사되었습니다!
복사되었습니다!
5
3
5
3
5