[LeetCode] 347. Top K Frequent Elements

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

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

---

접근 방법: Counter() 사용 후 정렬하여 리턴

class Solution:
    # Counter 사용, 소팅을 사용하므로 시간복잡도는 O(nlogn) 고정
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        num_freq = collections.Counter(nums)
        return [i[0] for i in sorted(num_freq.items(), key=lambda x: x[1], reverse=True)[:k]]

• collections.Counter() 를 사용하여 nums 에 들어있는 숫자들을 카운팅한다.

• 딕셔너리의 밸류를 내림차순으로 정렬한 후, k 만큼 슬라이싱하여 리턴한다.

• 위 방법은 무조건 전체 리스트를 정렬하므로 $O(nlogn)$의 시간복잡도를 가지게 된다.

---

접근 방법: Counter().most_common(n) 메소드를 사용

Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

class Solution:    
    # Counter의 most_common 메소드 이용, 시간복잡도는 k가 n보다 작을 때 O(nlogk)
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        num_freq = collections.Counter(nums).most_common(k)
        return [i[0] for i in num_freq]

• 처음 방법의 경우, 결과값을 리턴하기 위해 딕셔너리의 전체 밸류를 소팅한 후 슬라이싱을 하였다. 이렇게 되면, k 값이 n 에 비해 많이 작더라도 고정적으로 $O(nlogn)$의 시간복잡도를 가지는데, Follow up에서 $O(nlogn)$보다 작은 시간복잡도를 가져야한다는 조건을 걸어서 다른 방법을 찾아보기로 하였다.

• Counter() 클래스에 포함된 most_common(n) 이라는 메소드를 찾게 되었는데, 이는 카운터로 생성된 딕셔너리에서 밸류가 높은순서대로 n개의 원소만 리턴해주기 때문에 이 메소드를 이용하여 필요한 갯수만큼만 가져오기로 했다.

• most_common(n) 은 어제 풀었던 우선순위 큐를 사용하는 메소드다. 파이썬에 내장된 heapq 를 사용하여 우선순위 순서대로 원하는 갯수만큼 뽑아내게 되는데, 이 방식의 시간 복잡도는 총 n개의 원소에서 k개를 뽑아낼 때 $O(n log k)$로 문제에서 요구하는 조건인 $O(nlogn)$보다 작아지게 된다.

• https://stackoverflow.com/questions/29240807/python-collections-counter-most-common-complexity

---

class Solution:    
    # Counter의 most_common 메소드 이용, 시간복잡도는 k가 n보다 작을 때 O(nlogk)
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # zip과 *(언패킹)을 사용
        return list(zip(*collections.Counter(nums).most_common(k)))[0]

• 위 코드는 책에서 제시한 방법으로, zip 과 *(unpacking) 을 이용하여 한 줄로 만든 코드다.

• zip 의 경우, 여러개의 리스트에서 같은 인덱스의 원소를 가져와 하나로 합치는 함수다. 길이가 다를 경우 가장 짧은 리스트를 기준으로 반환해준다.

• *(unpacking) 은 말 그대로 리스트나 세트로 묶여있는 원소들을 풀어주는 것이다.

• 따라서 위 코드는 most_common() 으로 받아온 [[key1, value1], [key2, value2] ... ] 형태의 리스트를 언패킹해 [key1, value1], [key2, value2] ... 형태로 만들어 준 뒤, 각 리스트의 같은 인덱스만 zip 하여 최종적으로 [key1, key2, ... ], [value1, value2, ... ] 형태의 두 리스트로 만들어주는 코드이다.