← 전체 회차
a-067-kth-largest-element-in-an-array2026-07-19mediumleetcode #215neetcode150

배열에서 K번째 큰 원소

#array#divide-and-conquer#sorting#heap-priority-queue#quickselect
↗ leetcode #215 · a-067-kth-largest-element-in-an-array
01

문제

· problem
P.a-067-kth-largest-element-in-an-array

배열에서 K번째 큰 원소

↗ leetcode #215

정수 배열 nums와 정수 k가 주어질 때, 배열에서 k번째 큰 원소를 반환하세요. 정렬된 순서에서 k번째 큰 원소를 구하며, 서로 다른 k번째 원소가 아님을 주의하세요. 정렬 없이 풀 수 있을까요?

제약
  • · 1 ≤ k ≤ nums.length ≤ 10^5
  • · -10^4 ≤ nums[i] ≤ 10^4
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[3,2,1,5,6,4]
2
5
example 2input → output
[3,2,3,1,2,4,5,5,6]
4
4
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    k번째 큰 원소는 중복을 포함해서 세나요?
  • ☐
    입력 배열을 수정해도 되나요?
  • ☐
    배열에 음수가 포함될 수 있나요?
  • ☐
    배열이 스트림처럼 계속 들어오는 경우도 고려해야 하나요?
  • ☐
    정렬을 사용하면 가장 간단하지 않을까요?
  • ☐
    최대 힙을 사용하는 것이 더 직관적이지 않을까요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 배열을 최소 힙으로 변환
○
heapify(nums)
○
nums = heapq.heapify(nums)
○
heap = PriorityQueue()
for num in nums:
    heap.put(num)
step 2· 반복: k개만 남을 때까지│ 중첩
○
while len(nums) > k:
○
while len(nums) >= k:
○
for _ in range(len(nums) - k):
step 3· 최소 원소 제거│ │ 중첩
○
heappop(nums)
○
nums.pop(0)
○
min_val = min(nums)
nums.remove(min_val)
step 4· k번째 큰 원소 반환│ 중첩
○
return nums[0]
○
return nums[-1]
○
return max(nums)
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
# Solution: Sorting
2
# Time Complexity:
3
#   - Best Case: O(n*log(k))
4
#   - Average Case: O(n*log(k))
5
#   - Worst Case:O(n*log(k))
6
# Extra Space Complexity: O(k)
7
class Solution:
8
    def findKthLargest(self, nums: List[int], k: int) -> int:
9
        heapify(nums)
10
        while len(nums) > k:
11
            heappop(nums)
12
        return nums[0]
13
14
# Solution: Sorting
15
# Time Complexity:
16
#   - Best Case: O(n)
17
#   - Average Case: O(n*log(n))
18
#   - Worst Case:O(n*log(n))
19
# Extra Space Complexity: O(n)
20
class Solution1:
21
    def findKthLargest(self, nums: List[int], k: int) -> int:
22
        nums.sort()
23
        return nums[len(nums) - k]
24
25
26
# Solution: QuickSelect
27
# Time Complexity: O(n)
28
# Extra Space Complexity: O(n)
29
class Solution2:
30
    def findKthLargest(self, nums: List[int], k: int) -> int:
31
        pivot = random.choice(nums)
32
        left = [num for num in nums if num > pivot]
33
        mid = [num for num in nums if num == pivot]
34
        right = [num for num in nums if num < pivot]
35
36
        length_left = len(left)
37
        length_right = len(right)
38
        length_mid = len(mid)
39
        if k <= length_left:
40
            return self.findKthLargest(left, k)
41
        elif k > length_left + length_mid:
42
            return self.findKthLargest(right, k - length_mid - length_left)
43
        else:
44
            return mid[0]
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[3,2,1,5,6,4]
2
→
5
case 2
[3,2,3,1,2,4,5,5,6]
4
→
4
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.