[leetcode 2024/02/07] 347. Top K Frequent Elements - heapq.nlargest

https://leetcode.com/problems/top-k-frequent-elements/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

1. 접근 방법

리스트가 주어졌을 때, 문자들의 개수를 count 해주고, k에 따라서 가장 많이 있는 문자 k개를 출력해주는 문제이다.

 

즉, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4

이면, 3이 제일 많고 -> 1, 2가 다음 -> 4가 다음으로 많다.

이때, k = 2 이면 많은 것 순으로 2개 출력 하는 것이니 3은 당연히 출력되고, 1 또는 2를 출력해주면 된다. 

왜냐하면 조건으로 you may return the answer in any order가 있기 때문이다. 

 

따라서 for 문으로 nums를 돌면서 dictionary에 저장해주었다. dictionary는 defaultdict를 사용해주었다.

새로운 키 값마다 선언 안해주고 자동으로 선언 후, 값이 +=1 되게 하고 싶었기 때문이다.

dict_freq = defaultdict(int)
dict_freq[i] += 1

 

이후 dictionary를 sort().reverse() 하고 앞에 있는 k 개만 출력해주면 되는 문제이지만, k개만 출력해도 된다면 k개만 찾고 멈출 수 있는 방법이 없을까? 하고 궁금해졌다. 뭔가, 다 정렬하는 것이 시간 낭비라는 생각이 들었기 때문이다.

 

일반적으로 sort하는 방법:

sorted_items_desc = sorted(my_dict.items(), key=lambda item: item[1], reverse=True)

 

 

sorted 함수도 복잡하다.

sorted(iterable, *, key=None, reverse=False)
sorted(반복문, key = , 역순?)

이를 보면서 하나씩 해석해보면, sorted 함수에 반복문으로 my_dict.items() 를 넣어주었다.

lambda 변수들 : 함수 구조를 기준으로 보면, 변수로 item 을 받고 ('1':2)  , item[1] 을 얻고 이를 기준으로 정렬해주었다.

이때, 정렬은 내림차순으로 하겠다고 하였다. ( reverse = True)

 

heapq.nlargest를 이용하는 방법:

largest_k = heapq.nlargest(k, dict_freq.items(), key = lambda item: item[1])

 

heapq.nlargest(k, iterable, key=None) => 주어진 데이터의 반복문 (iterable) 에서, 가장 큰 k 개의 요소를 찾아 리스트로 반환한다. 

 

코드를 찬찬히 뜯어보자.

k 는 몇개의 큰 수를 출력할 것인지...

dict_freq.items() 는 [(1, 3), (2, 2), (3, 1)] 이런식으로 구성되어 있는 반복문.. 즉 이 iterable을 대상으로,

key 를 기준으로 정렬한다는 것이다.

 

key는 item 에 대해서 item[1] 을 반환하기에, item[1]을 기준으로 정렬한다.

 

+ heapq 에 대해서 알아보자

표준 라이브러리 중 하나로, 힙 큐 알고리즘 - 최소 힙을 구현한 것.

heapify(x): 리스트 x를 선형 시간 내에 현장에서 힙으로 변환합니다.
heappush(heap, item): item을 heap에 추가하며, 힙의 불변성을 유지합니다.
heappop(heap): heap에서 가장 작은 항목을 제거하고 반환합니다. 힙이 비어 있으면, IndexError를 발생시킵니다.
heappushpop(heap, item): 새 item을 힙에 추가한 다음, heap에서 가장 작은 항목을 제거하고 반환합니다. 이는 heappush()를 따라 heappop()를 호출하는 것보다 더 효율적입니다.
heapreplace(heap, item): heap에서 가장 작은 항목을 제거하고 반환한 후, 새 item을 추가합니다. heappop()을 호출한 다음 heappush()를 호출하는 것보다 더 효율적입니다.
nlargest(n, iterable, key=None): 데이터의 반복 가능한 시퀀스에서 n개의 가장 큰 요소를 반환합니다.
nsmallest(n, iterable, key=None): 데이터의 반복 가능한 시퀀스에서 n개의 가장 작은 요소를 반환합니다.

이런 기능들도 추가적으로 있음을 알 수 있다. -> 최소 힙의 기능 중 하나를 사용했음을 알 수 있다.

 

sorted() vs heapq.nlargest()

무엇이 더 나을까? 우리의 친구 chatGPT에게 판단을 부탁해보자.

 

sorted()

- 전체 정렬 순서를 요구할 때 유용. 

- 전체 리스트를 메모리에 저장해야 한다.

- 전체 데이터셋이 크고 k가 상대적으로 작을 때는 비효율적.

- 시간 복잡도: O(n log n)

 

heapq.nlargest()

- 힙 정렬 알고리즘 사용 -> 가장 큰 k 개의 요소만을 찾음

- 전체 데이터를 정렬하지 않기 때문에, k 가 전체 데이터셋에 비해 작을 때 효율적

- 큰 데이터셋에서 소수의 최대값을 찾을 때 유리

- 시간 복잡도 : O(nlog k)

 

총평:

- 데이터셋이 작거나 전체 정렬 순서가 필요할 때 -> sorted()

- 데이터셋이 크코 k가 작을 때 -> heapq.nlargest()

 

따라서, heapq.nlargest() 를 사용한 것이 나쁘지 않은 선택이었음을 알 수 있다.

 

2. 코드

from collections import defaultdict
import heapq
from typing import List


class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        dict_freq = defaultdict(int)
        for i in nums:
            dict_freq[i] += 1
        largest_k = heapq.nlargest(k, dict_freq.items(), key = lambda item: item[1])

        return list(map(lambda x: x[0], largest_k))


solution = Solution()
print(solution.topKFrequent([1,1,1,2,2,3],2))