Funcia
Lv.3heappriority-queue

실시간 중앙값

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

정수가 nums 순서대로 하나씩 들어옵니다. 수가 하나 들어올 때마다 지금까지 들어온 수들의 중앙값을 구해, 차례대로 배열에 담아 반환하세요.

들어온 수가 k개일 때, 정렬해서 앞에서 ⌈k/2⌉\lceil k/2 \rceil번째 수를 중앙값으로 합니다. 즉 짝수 개면 가운데 두 수 중 작은 쪽입니다.

입출력 예

numsresult
[1, 5, 2, 10, -99, 7, 5][1, 1, 2, 2, 2, 2, 5]
[3, 3, 3][3, 3, 3]

입출력 예 설명

예 1 — [1, 5]의 중앙값은 작은 쪽인 1, [1, 2, 5]는 2, [1, 2, 5, 10]은 2, [-99, 1, 2, 5, 10]은 2, … 마지막 [-99, 1, 2, 5, 5, 7, 10]은 5입니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(nums: int[]) → int[]

제한 사항

  • 1≤1 \le nums.length ≤200,000\le 200{,}000
  • −109≤-10^9 \le nums[i] ≤109\le 10^9

기대 복잡도

시간
O(N log N)
공간
O(N)

입출력 예

nums기대 출력
[1,5,2,10,-99,7,5][1,1,2,2,2,2,5]
[3,3,3][3,3,3]

힌트

힌트

힙 두 개로 수들을 반으로 나눠 담으세요.

  • low: 작은 절반을 담는 최대 힙 (맨 위 = 작은 절반 중 가장 큰 수)
  • high: 큰 절반을 담는 최소 힙

항상 low의 크기가 high와 같거나 1 크게 유지하면, low의 맨 위가 바로 (작은 쪽) 중앙값입니다.

새 수 x는 low의 맨 위보다 작거나 같으면 low에, 아니면 high에 넣은 뒤, 크기 조건이 깨지면 한쪽 맨 위를 다른 쪽으로 옮깁니다. 수 하나당 O(log⁡N)O(\log N)입니다.

복잡도 목표

수가 들어올 때마다 전체에서 중앙값을 다시 고르면 적어도 O(N2)O(N^2)이라 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251478 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample02입력·출력 공개
correctness407판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.