[1스4코2파] # 236. LeetCode 215. Kth Largest Element in an Array

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (236차)
[4코1파] 2023.01.13~ (228일차)
[1스4코1파] 2023.04.12~ (139일차)
[1스4코2파] 2023.05.03 ~ (117일차)

Today :

2023.08.27 [236일차]
215. Kth Largest Element in an Array
https://leetcode.com/problems/kth-largest-element-in-an-array/

215. Kth Largest Element in an Array

문제 설명

정수로 구성된 배열 nums와 정수 k가 주어졌을 때,
배열에서 k번째로 큰 수를 return 함
sort를 사용하지 않고 풀어야 함 !

문제 풀이 방법

문제의 제약조건이 sort를 하지않고 정수로 구성된 배열에서 k번째로 큰 정수를 반환해야 하는데, 이건 heap 구현체로 푼다.
minHeap 으로 만들어서 해당 배열의 길이가 k보다 클때까지 heappop을 통해서 풀면 시간복잡도 O(logn)으로 찾을 수 있음 굿

내 코드

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)
        while len(nums) > k:
            heapq.heappop(nums)
        return nums[0]

증빙

여담

이게 왜 medium 임? easy임