← 전체 회차
a-064-kth-largest-element-in-a-stream2026-07-16easyleetcode #703neetcode150

스트림에서 k번째 최대 요소

#tree#design#binary-search-tree#heap-priority-queue#binary-tree#data-stream
↗ leetcode #703 · a-064-kth-largest-element-in-a-stream
01

문제

· problem
P.a-064-kth-largest-element-in-a-stream

스트림에서 k번째 최대 요소

↗ leetcode #703

대학 입시 사무실의 일원으로서, 지원자의 시험 성적 중 k번째 최고 성적을 실시간으로 추적해야 합니다. 이는 면접 및 입시의 커트라인을 동적으로 결정하는 데 도움이 됩니다. 새로운 성적이 제출될 때마다 주어진 정수 k에 대해 스트림의 k번째 최고 성적을 유지하고 지속적으로 반환하는 클래스를 구현해야 합니다. 더 구체적으로, 우리는 모든 성적의 정렬된 목록에서 k번째 최고 성적을 찾고 있습니다. KthLargest 클래스를 구현하십시오: KthLargest(int k, int[] nums): 정수 k와 시험 성적의 스트림 nums로 객체를 초기화합니다. int add(int val): 새로운 시험 성적 val을 스트림에 추가하고 지금까지의 성적 풀에서 k번째 최대 요소를 나타내는 요소를 반환합니다.

제약
  • · 0 ≤ nums.length ≤ 10^4
  • · 1 ≤ k ≤ nums.length + 1
  • · -10^4 ≤ nums[i] ≤ 10^4
  • · -10^4 ≤ val ≤ 10^4
  • · At most 10^4 calls will be made to add()
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
["KthLargest","add","add","add","add","add"]
[[3,[4,5,8,2]],[3],[5],[10],[9],[4]]
[null, 4, 5, 5, 8, 8]
example 2input → output
["KthLargest","add","add","add","add"]
[[4,[7,7,7,7,8,3]],[2],[10],[9],[9]]
[null, 7, 7, 7, 8]
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    k번째 최대값은 중복을 포함하는 순위로 계산되는가?
  • ☐
    최소 힙의 루트가 항상 k번째 최대값인 이유는?
  • ☐
    입력 배열을 직접 수정하는 것이 안전한가?
  • ☐
    최대 힙으로 모든 요소를 추적하면 더 효율적이지 않을까?
  • ☐
    매번 전체 배열을 정렬하면 안 되는 이유는?
  • ☐
    초기화 후 요소가 k개 미만이면 add()는 어떻게 작동하는가?
  • ☐
    heapify()가 O(n) 시간에 작동하는가?
  • ☐
    add() 후 len > k 체크에서 while이 아닌 if를 쓰는 이유는?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 힙 변수와 k 초기화
○
self.minHeap, self.k = nums, k
○
self.minHeap = heapq.heappush(nums, k)
○
self.minHeap = nums[:k]
step 2· 배열을 힙 구조로 변환
○
heapq.heapify(self.minHeap)
○
heapq.heappop(self.minHeap)
○
self.minHeap = sorted(self.minHeap)
step 3· 초기화 중 초과 요소 제거
○
while len(self.minHeap) > k:
○
if len(self.minHeap) > self.k:
○
while len(self.minHeap) > self.k: heapq.heappush(self.minHeap, self.minHeap[0])
step 4· 새 값을 힙에 추가│ 중첩
○
heapq.heappush(self.minHeap, val)
○
heapq.heappop(self.minHeap, val)
○
self.minHeap.append(val)
step 5· 추가 후 크기 초과 시 최소값 제거│ 중첩
○
if len(self.minHeap) > self.k:
○
if len(self.minHeap) >= self.k:
○
while len(self.minHeap) > self.k: heapq.heappop(self.minHeap)
step 6· k번째 최대값 반환│ 중첩
○
return self.minHeap[0]
○
return self.minHeap[-1]
○
return self.minHeap.pop()
○
return sorted(self.minHeap)[0]
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class KthLargest:
2
    def __init__(self, k: int, nums: List[int]):
3
        # minHeap w/ K largest integers
4
        self.minHeap, self.k = nums, k
5
        heapq.heapify(self.minHeap)
6
        while len(self.minHeap) > k:
7
            heapq.heappop(self.minHeap)
8
9
    def add(self, val: int) -> int:
10
        heapq.heappush(self.minHeap, val)
11
        if len(self.minHeap) > self.k:
12
            heapq.heappop(self.minHeap)
13
        return self.minHeap[0]
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
["KthLargest","add","add","add","add","add"]
[[3,[4,5,8,2]],[3],[5],[10],[9],[4]]
→
[null, 4, 5, 5, 8, 8]
case 2
["KthLargest","add","add","add","add"]
[[4,[7,7,7,7,8,3]],[2],[10],[9],[9]]
→
[null, 7, 7, 7, 8]
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.