LeetCode [ 215 | Python ] Kth Largest Element in an Array

문제

https://leetcode.com/problems/kth-largest-element-in-an-array/?envType=study-plan-v2&envId=top-interview-150

주어진 배열 nums에서 또한 주어진 정수 k번 째로 큰 정수를 반환해야하는 문제.

풀이

지속적으로 한다면 가장 큰 값을 찾는 것도, 가장 작은 값을 찾는 것도 heap이 유리하다.
이는 pop 연산을 수행하면 가장 작은 값을 반환하는 heap의 특성 때문인데, 가장 큰 값을 찾기 위해서는 단순히 저장할 때 -를 취한 값을 저장해주면 된다.

이를 이용해 문제를 해결하고자 했다.

정답

실행시간 : 909ms 메모리 : 23.8MB

1. nums의 모든 원소에 -를 취해 heap에 저장한다.
2. k-1만큼 heappop연산을 수행한다.
   1. k-1인 이유는 return 값을 k번째 값을 마지막으로 pop하기 위함이다.
3. pop연산을 수행한 값에 -을 취해 반환한다.

값을 하나씩 넣은 뒤 다시 빼는 것은 다소 비효율적인 코드로 보였다.
또한 더욱 유용한 함수를 알고 있었기 때문에, 이를 활용하기로 했다.

import heapq
class Solution(object):
    def findKthLargest(self, nums, k):
        heap = []
        for n in nums:
            heapq.heappush(heap, -n)
        
        for _ in range(k-1):
            heapq.heappop(heap)
        
        return -heapq.heappop(heap)
            

nlargest 활용 (개선 ?)

실행시간 : 740ms
메모리 : 28.5MB

파이썬은 nlargest라는 n개의 큰 값을 찾아내는 함수가 존재한다.
이는 heapq 자료구조에 대해 수행되어야 하기 때문에 입력받은 nums를 heapify 연산을 통해 힙 구조로 만들고 그에 대해 nlargest 함수를 적용하면 된다.

하지만 최대값들을 담을 새로운 배열을 생성하기 때문에 그만큼 많은 메모리를 사용하는 모습을 볼 수 있다.

import heapq
class Solution(object):
    def findKthLargest(self, nums, k):
        heapq.heapify(nums)
        return heapq.nlargest(k,nums)[-1]
            
        

생각 & 정리

지속적으로 큰 값을 얻어내야한다는데 어려움이 있을 수 있었으나 힙, 우선순위 큐에 대해 알고있음으로 다소 쉽게 해결할 수 있는 문제였다.
이렇듯 다양한 문제를 해결하는데 자료구조가 활용된다.

어떻게 저장하고, 어떻게 빼내고 또한 어떻게 관계를 맺어주는가에 대해 설정해주는 것 뿐으로 복잡해질 수 있는 연산을 간단하게 해결가능한 것이다.
학교 수업에서도, 따로 구현도 해보는 시간을 가졌지만 더 다양한 자료구조에 대해 알아보고 싶다는 생각이 들었다.