31. Top K Frequent Elements

- 파이썬 알고리즘 인터뷰 31번 문제

2020.02.02

3 try

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        arr = defaultdict(int)
        ans = []
        for num in nums:
            arr[num] += 1
        result = sorted(arr.items(), key=lambda x: x[1], reverse=True)
        for x in result:
            ans.append(x[0])
        return ans[:k]

- (key = 숫자값, value = 각 숫자가 등장한 횟수)인 dict를 생성한다.
- value를 기준으로 dict를 내림차순으로 정렬한다.
- 정렬한 dict의 숫자값(key)만을 따로 순서대로 list로 추출하여 저장한다.
- 리스트 슬라이싱을 사용하여 list[:k]를 반환한다.

✔ dict를 정렬하는 방법

1. key를 이용한 정렬
- sorted(dict.items())
  + items()는 튜플(key, value)로 구성된 리스트를 리턴한다. 
 
2. value를 이용한 정렬
- sorted(dict.items(), key=lambda x: x[1])
  + 추가로.. reverse = True를 삽입하면 내림차순(큰것부터)으로 정렬된다.

- 

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freqs = Counter(nums)
        freqs_heap = []
        for f in freqs:
            heapq.heappush(freqs_heap, (-freqs[f], f))
            # value를 기준으로 한 min heap을 만들기 위해 (value, key) 순으로 heappush 함
            # -freqs[f] : 음수 처리를 해줌으로써 min heap이지만 max heap을 사용한 것 같은 효과!

        topk = list()
		
        # 가장 많이 나온 순서대로 k번째 순서까지 heapq에서 pop하여 사용
        # heapq에서 pop한 값은(value, key)이므로 [1] -> key만 추출하여 topk에 저장
        for _ in range(k):
            topk.append(heapq.heappop(freqs_heap)[1])

        return topk

✔ Counter에 대해 알게 되었다. dict랑 거의 비슷하다.

>>> Counter([1, 3, 3, 2, 2, 2, 4])
Counter({2: 3, 3: 2, 1: 1, 4: 1})

>>> freqs = Counter([1, 3, 3, 2, 2, 2, 4])
>>> for key in freqs: # dict와 동일하게 freqs를 for문으로 사용하면 key값만을 사용
>>> 	print(key)
1
3
2
4

# value 값도 사용하고 싶다면? - dict와 동일!
>>> freqs = Counter([1, 3, 3, 2, 2, 2, 4])
>>> for key, value in freqs.items(): 
>>> 	print(key, value)
1 1
3 2
2 3
4 1

>>> freqs[0]
0 	# -> 해당 key값에 대한 value가 존재하지 않아도 0을 리턴
>>> freqs[1]
1	# -> 해당 key값에 대한 value가 존재하면 value를 리턴

>> c = Counter(a=4, b=2, c=0, d=-2)
>> list(c.elements())
['a', 'a', 'a', 'a', 'b', 'b']

>> Counter('abracadabra').most_common(3)
[('a', 5), ('r', 2), ('b', 2)]

>> c = Counter(a=4, b=2, c=0, d=-2)
>> d = Counter(a=1, b=2, c=3, d=4)
>> c.subtract(d)
>> c
Counter({'a': 3, 'b': 0, 'c': -3, 'd': -6})