테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== Top K Frequent Elements ======

===== 풀이 =====
  * 그냥 시키는대로 하면 되는 문제. 가장 간단한 구현 방법은, collection.Counter을 이용해서 frequency 들을 카운팅 한 뒤에, Counter의 most_common 함수를 사용하는 것이다. most_common 함수는 내부적으로 heapq.nlargest 함수를 이용한다. 시간복잡도는 O(n+klogn) 이다.
  * 사실 실용적으로는 이 정도로 충분하다. 하지만 [[https://leetcode.com/problems/top-k-frequent-elements/editorial/|공식 솔루션]] 에서는 quick select 를 이용하는 O(n) 방법을, [[https://neetcode.io/solutions/top-k-frequent-elements|neetcode의 솔루션]] 에서는 min-heap을 이용하는 O(nlogk) 방법과 카운팅소트를 이용하는 O(n) 방법도 언급하고 있긴 하다.

===== 코드 =====
{{gh>https://github.com/teferi00/problem_solving/blob/main/problems/leetcode/q0347.py}}

{{tag>LeetCode}}