[LeetCode] topKFrequent(상위 K 빈도 요소)

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

LeetCode - The World's Leading Online Programming Learning Platform

문제 해설:

문자의 갯수가 k번 이상 등장하는 갯수를 구한다.

 

* 받아온 리스트의 문자들의 갯수를 써준다.

* 딕셔너리의 value가 빈도수이기 때문에 value순으로 가장 높은 숫자가 앞에 나오도록 정렬한다.

 

* 딕셔너리에 요소들을 꺼내며 value의 값이 k보다 작거나 크면 정답 리스트에 추가해준다.

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        num_count = dict(collections.Counter(nums))
        answer = []
        d2 = sorted(num_count.items(), key=lambda x: x[1], reverse=True)

        count = 0
        for value, cnt in d2:
            if count == k:
                break
            answer.append(value)
            count += 1
        return sorted(answer)

 

---

좀 더 개선이 필요하다.

정답을 찾는 for문과, d2를 개선 할 필요가 있다 

 

우선순위큐을 사용해보자

heappop() 함수는 O(logN) 의 시간 복잡도를 가집니다.

파이썬에서 힙은 최소힙(Min Heap)만 지원하기 때문에 키를 빈도수로 하되 -빈도수로 추가해줘서 가장 상위에 올 수 있도록 한다.

        heap = []
        num_count = collections.Counter(nums)

        for f in num_count:
            print(-num_count[f], f)
            heapq.heappush(heap, (-num_count[f], f))

꺼낼때 또한 상위 K개만 힙에서 꺼내주면 되기때문에 손쉽게 찾을 수 있다.

	topk = list()
        for _ in range(k):
            topk.append(heapq.heappop(heap)[1])