실시간 하위 중앙값 알림
자바스크립트 코딩테스트 문제로 two-heaps 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
점수가 하나씩 들어올 때마다 그 시점의 하위 중앙값을 바로 구하는 문제입니다.
문제 설명
정수 배열 scores가 주어집니다.
배열의 앞에서부터 점수를 하나씩 추가해 가며, 각 시점까지 들어온 점수들의 하위 중앙값(lower median) 을 구해 배열로 반환하세요.
하위 중앙값은 다음처럼 정의합니다.
- 원소 개수가 홀수이면 가운데 값
- 원소 개수가 짝수이면 가운데 두 값 중 더 작은 값
예를 들어:
[5]의 하위 중앙값은5[5, 2]를 정렬한[2, 5]의 하위 중앙값은2[5, 2, 10]을 정렬한[2, 5, 10]의 하위 중앙값은5
scores[i]까지 봤을 때의 하위 중앙값을 순서대로 담은 배열을 반환하는 runningLowerMedianAlerts 함수를 작성하세요.
제한사항
0 <= scores.length <= 100,000-1,000,000,000 <= scores[i] <= 1,000,000,000- 반환 배열의 길이는
scores.length와 같습니다. - 짝수 개일 때는 반드시 작은 쪽 중앙값을 사용해야 합니다.
예시
- 입력:
scores = [5, 2, 10, 4]→ 출력:[5, 2, 5, 4] - 입력:
scores = [7, 7, 7, 7]→ 출력:[7, 7, 7, 7] - 입력:
scores = [-3, 8, 1, 6, 0]→ 출력:[-3, -3, 1, 1, 1] - 입력:
scores = [9, 1]→ 출력:[9, 1]
힌트
- 매번 지금까지의 값을 전부 정렬하면 너무 느립니다.
- 작은 절반과 큰 절반을 따로 관리하면 중앙값을 빨리 알 수 있습니다.
- 짝수 개일 때 하위 중앙값을 써야 하므로, 작은 절반 쪽이 하나 더 많거나 크기가 같도록 유지해 보세요.
해설
핵심은 숫자들을 두 개의 힙으로 나누어 관리하는 것입니다.
left: 작은 절반을 담는 최대 힙right: 큰 절반을 담는 최소 힙
이때 다음 규칙을 유지하면 됩니다.
left의 모든 값은right의 모든 값보다 작거나 같습니다.left.length는right.length와 같거나 정확히 1 더 많습니다.
이 규칙이 유지되면:
- 원소 수가 홀수일 때도
left의 루트가 중앙값 - 원소 수가 짝수일 때도
left의 루트가 하위 중앙값
이 됩니다.
예를 들어 scores = [5, 2, 10, 4]를 보겠습니다.
5추가left = [5],right = []- 하위 중앙값:
5
2추가- 작은 쪽에 넣은 뒤 균형 조정
- 정렬 상태로 보면
[2, 5] - 하위 중앙값:
2
10추가- 큰 쪽으로 들어감
- 정렬 상태로 보면
[2, 5, 10] - 하위 중앙값:
5
4추가- 균형을 다시 맞추면 정렬 상태는
[2, 4, 5, 10] - 하위 중앙값:
4
- 균형을 다시 맞추면 정렬 상태는
즉 결과는 [5, 2, 5, 4]입니다.
매 숫자마다 힙에 넣고 몇 번의 재균형만 하면 되므로, 각 단계는 O(log n)에 처리할 수 있습니다. 전체 시간 복잡도는 O(n log n)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
JavaScript
에디터 로딩 중...
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
아직 실행하지 않았습니다.
실행 결과
아직 실행하지 않았습니다.
예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.