배열의 K번째 큰 요소

<aside> 💡 문제 링크

</aside>

문제 정리

<aside> 💡 정렬되지 않은 배열에서 k번째 큰 요소를 추출하라.

</aside>

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

접근 방법

<aside> 💡 해당문제는 상당히 많은 방법으로 접근할 수 있다.

파이썬 리스트 정렬 이용
직접 heap 구현
heapq 모듈 이용
heapq 모듈의 heapify 이용
heapq 모듈의 nlargest 이용 </aside>

파이썬의 리스트 정렬 이용

<aside> 💡 그냥 문제를 보자마자 풀어보았던 방식이다. 아직 힙에 대해서 공부하지 않았을 때인데

굉장히 간단하게 해결할 수 있었다.

</aside>

class Solution:
    def findKthLargest(self, nums, k):
        nums.sort(reverse=True) #리스트 내림차순으로 정렬
        return nums[k-1] # 출력

sol = Solution()
print(sol.findKthLargest(nums = [3,2,3,1,2,4,5,5,6], k = 4))

직접 heap 구현

<aside> 💡 힙에 대해서 정리해놓은 페이지에 자세하게 설명을 적어놨다.

</aside>

class BinaryMaxHeap:
    def __init__(self):
        # index 계산 편의를 위해 1부터 사용하도록 한다.
        self.items = [None]

    def __len__(self):
        # len() 연산을 가능하게 하는 매직 메서드 덮어쓰기.
        # 1부터 시작이므로 +1 해준다.
        return len(self.items) - 1

    # 맨끝에 삽입한 요소를 부모 노드와 비교해가면서 올린다.
    def _percolate_up(self):
        cur = len(self)  # 현재 인덱스

        parent = cur // 2  # 부모 인덱스

        while parent > 0:  # 부모가 0번째 인덱스보다 클 경우.
            # 현재 노드와 부모 노드를 바꿔준다.
            if self.items[cur] > self.items[parent]:
                self.items[cur], self.items[parent] = self.items[parent], self.items[cur]

            # 인덱스를 바꿔준다.
            cur = parent
            parent = cur // 2

    def _percolate_down(self, cur):
        biggest = cur
        left = 2 * cur
        right = 2 * cur + 1

        if left <= len(self) and self.items[left] > self.items[biggest]:
            biggest = left

        if right <= len(self) and self.items[right] > self.items[biggest]:
            biggest = right

        if biggest != cur:
            self.items[cur], self.items[biggest] = self.items[biggest], self.items[cur]
            self._percolate_down(biggest)

    def insert(self, k):
        self.items.append(k)  # 맨 끝에 요소 추가.
        self._percolate_up()  # 위로 끌어 올리기

    def extract(self):
        # 길이가 1보다 짧을경우 예외
        if len(self) < 1:
            return None

        root = self.items[1]  # 루트노드
        self.items[1] = self.items[-1]  # 루트 노드와 새로 추가한 노드 교체
        self.items.pop()  # 루트 노드 삭제
        self._percolate_down(1)  # 아래로 비교하며 탐색

        return root

class Solution:
    def findKthLargest(self, nums, k):
        bmh = BinaryMaxHeap()

        for e in nums:
            bmh.insert(e)

        return [bmh.extract() for _ in range(k)][k-1]

sol = Solution()
print(sol.findKthLargest(nums=[3, 2, 1, 5, 6, 4], k=2))

heapq 모듈 이용

<aside> 💡 heapq doc 문서

heapq는 힙의 알고리즘을 구현하는 코드이다. (최소 힙)

주의할점은 앞서 직접구현한 알고리즘에서는 1부터의 인덱스를 가지도록 설계를 했다면,

heapq는 0부터의 인덱스를 가진다.

</aside>

<aside> 💡 heapq.headpush(heap, item) 메소드

힙 불변성을 유지하면서, item값을 heap으로 push한다.

앞서 직접구현한 insert()메소드를 대체한다.

</aside>