55. Kth Largest Element in an Array

🎯 leetcode - 215. Kth Largest Element in an Array

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 55번 문제

📌 날짜

2020.02.24

📌 시도 횟수

1 try

💡 Code

1. heapq 이용하기

import heapq

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        hq = []
        for i in nums:
            heapq.heappush(hq, (-i))

        for i in range(k - 1):
            heapq.heappop(hq)
        return -heapq.heappop(hq)

2. list.sort()

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums.sort(reverse=True)
        return nums[k-1]

💡 문제 해결 방법

1. heapq 이용하기
- nums의 값을 heapq.heappush 한다.
- 큰 값부터 추출되어야 하므로, 음수 (-i)를 heappush한다.
- 단, heappop한 뒤 리턴하는 최종 값에는 다시 -를 붙여준다.

2. nums.sort()
- 그냥 nums 리스트를 sort하고 k번째로 큰 값을 리턴했다.
- 큰 값부터 정렬되도록 reverse = True를 지정해줬다.

💡 새롭게 알게 된 점

-

❌ (한번에 맞추지 못한 경우) 오답의 원인

-

---

😉 다른 풀이

📌 하나. heapq 모듈의 heapify

import heapq

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)
        for _ in range(len(nums) - k):
            heapq.heappop(nums)
        return heapq.heappop(nums)

💡 문제 해결 방법

- nums 리스트가 heapq 특성을 만족하는 리스트가 되도록 값의 위치를 바꾸어 주었다.
- 이 경우 원래 heapq의 특성대로 최소힙이 적용되었다.
따라서 for문의 범위가 len(nums)-k 가 된 것이다.

💡 새롭게 알게 된 점

🚗 heapify(자료구조) : 주어진 자료구조가 힙 특성을 만족하도록 바꿔주는 연산
- heapify(list) : list가 힙 특성을 만족하도록 "값의 위치를 변경"한다.
- 따라서 위의 예시를 print(nums)로 비교해보면...
>>> [3, 2, 1, 5, 6, 4]	# heapify 하기 전
>>> [1, 2, 3, 5, 6, 4]	# heapify 한 후

---

📌 둘. heapq 모듈의 nlargest

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return heapq.nlargest(k, nums)[-1]

💡 문제 해결 방법

- heapq.nlargest를 이용함

💡 새롭게 알게 된 점

- heapq.nlargest(n, iterable) : n번째 큰 값을 추출하는 기능의 함수이다.
> heapq.nlargest(n, iterable) : Return a list with the n 
largest elements from the dataset defined by iterable.