Hyuntae H

Hyuntae H

배워가는 학생
21.03.29~22.09.28 군대

Python Algorithm Q31

Q31 Top K Frequent Elements

Q

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

Sample Input

Example 1

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2

Input: nums = [1], k = 1
Output: [1]

Constraints

  • 1 <= nums.length <= 105
  • k is in the range [1, the number of unique elements in the array].
  • It is guaranteed that the answer is unique.

1. My Own Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        ans = []
        cnt = 0
        dic = sorted(collections.Counter(nums).items(), reverse=True,key=lambda item: item[1])
        print(dic)

        for tup in dic:
            ans.append(tup[0])
            cnt += 1
            if cnt >= k:
                break

        return ans

깔끔하게 counter 모듈 써서 풀었다. 사실 핵심은 value값(counter 모듈에서 나타나는 빈도)을 기준으로 한 sorting이다. 빈도 수가 높은 순으로 sorting 시킨다음, 맨 앞에서부터 k개의 key 값을 ans에 append해서 리턴했다. 읽으면 아마 한 방에 이해될 것이다.

늘 그랬듯이 런타임은 썩 좋지는 않다. 하위 34.9퍼 정도…?

2. Given Solution #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freqs = collections.Counter(nums)
        freqs_heap = []
        #insert to heap as negative

        for f in freqs:
            #f is the key, freqs[f] is the value(frequency)
            #insert it SWAPPED
            heapq.heapqpush(freqs_heap, (-freqs[f], f))

        topk = list()
        for _ in range(k):
            #pop out k-times
            #min-heap, so pop from the smallest value
            topk.append(heapq.heappop(freqs_heap[1]))

        return topk

힙에 대해 이해도가 조금 쌓여있으면 이해가 가는 풀이이다. freqs는 내 풀이처럼 counter 모듈을 이용한 풀이이다. 두 개의 for loop에서 이루어지는 일을 살펴보자.

1)for f in freqs
heapq.heapqpush(A, B) : heapq 라이브러리의 heapqpush 함수를 가져온 것이다. B 원소를 A에 heapqpush 한다는 뜻이며 heapqpush로 삽입하게 되면 매번 heapify가 발생한다.

**heapify는 특정 노드를 중심으로 그 근처의 트리들이 힙 성질을 만족하게 하는 작업이다. 내가 이용하는 heap은 min-heap이기 때문에, 완전 이진 트리 형태를 만족하면서 부모의 값(root)이 가장 작아야하고 자식 노드는 무조건 부모 노드보다 커야한다.

아무튼 내 코드에서는 미리 만들어놓은 빈 리스트인 freqs_heap(A)에다가 튜플(-freqs[f], f)(B)를 heapqpush 하고 있다. key(실제 숫자 값 f)와 value(숫자의 빈도수 freqs)의 위치를 바꾼 이유는 빈도수에 따라 정렬하고 싶어서라는건 알겠는데, 왜 빈도수에 -를 붇인 것일까? 이는 아래도 잠깐 설명하겠지만 min-heap이기 때문에 가장 큰 빈도수(positive 상태)가 먼저 추출(pop)되려면 negative로 바꾸어야 먼저 추출되기 때문이다!

*그냥 negative 안시키고 max-heap하면 안되냐? : heapq 모듈에서 min-heap만 지원하기 때문이다… 물론 어찌어찌 지원되긴 하지만 다른 제약이 많아서 min-heap으로 하는게 안정적이다.

2)for _ in range(k)
topk.append(headq.heappop(freqs_heap)[1]) : 답을 담을 리스트인 topk에다 append하는 모습이다. freqs_heap의 실질적인 자료형은 리스트이지만 heap구조로 구현했기 때문에 min-heap의 형태를 띄고 있다. 이는 아래 “heap에 대한 짤막한 이해”의 설명을 참고하자. freqs_heap 리스트에 있는 원소는 tuple형태이기 때문에 key를 가져가기 위해서는 freqs_heap[1] 형태로 가져와야 한다.

3. Given Solution #2

1
2
3

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        return list(zip(*collections.Counter(nums).most_common(k)))[0]

책 피셜 “가장 파이썬다운 방식”. 내가 봐도 그래보인다. 파이썬의 압도적인 라이브러리를 때려박아서 코드 한 줄로 끝내버리는 특유의 감성… 아무튼 이를 잘 쪼개서 이해해보자.

1

collections.Counter(nums).most_common(k)

nums는 문제에서 주어진 것 처럼 [1,1,1,2,2,3]이라고 하자.
Counter에는 most_common()이라는 빈도 수가 높은 순서대로 아이템을 추출하는 기능이 있다. 이를 통해서 출력한 결과는

[(1,3), (2,2)]

여기서 앞에 1과 2를 추출하기만 하면 된다. 위 코드의 출력값을 A라 하자. 그럼 나머지 코드는

1

list(zip(*A))[0]

처럼 된다. zip함수와 *(Asterisk)는 추후에 따로 설명할테니 간단히만 설명하겠다.

  • zip함수는 n개 이상의 시퀀스(연속된 자료형 like 리스트, 튜플, etc)를 일대일 대응 시켜놓은 새로운 튜플을 만드는 역할을 한다. 그래서 (1,3)과 (2,2)의 [0]들과 [1]들을 대응시켜 (1,2), (3,2)를 만들어 준다. zip은 제너레이터를 리턴하기 때문에 list를 붙여줘야 한다. list(range(10)) 처럼.

  • *(Asterisk)는 unpacking 동작을 수행한다. 위에서 zip(x1, x2)는 두 시퀀스 x1과 x2를 대응시켜준다고 했는데 인자가 단 하나뿐이면 어떻게 할까? list(zip(A))과 같은 경우는 대응시킬 다른 시퀀스가 없기 때문에 ,뒤에 공백이 온다.

    1

    [((1,3), ), ((2,2), )]

    그렇기 때문에 한 번 unpack 해서 인자를 둘로 나누는 것이다.
    A = [(1,3), (2,2)]이니까 A = (1,3), (2,2)이다.
    그래서 zip(    A)는 곧 x1=(1,3), x2= (2,2)인 zip(x1, x2)와 같다!

heap에 대한 짤막한 이해

image

여기 예시를 보자. 이 예시는 max-heap 구조인 완전 이진 트리이다. 만약 내가 [1, 2, 32, 58, 72, 98, 61, 53, 42] 라는 리스트가 있었는데, 이를 max-heap 형태로 heapqpush하면(*heapqpush를 사용할 경우 알아서 heapify 된다) 이 그림과 같이 된다. 이는 배열 구조가 맨 위의 root에서부터 아래로, 왼->오 순으로 읽히는 리스트와 같다. 즉

1

[98, 72, 61, 58, 2, 53, 42, 1, 32]

이런식의 리스트 형태로 저장되어 있는 셈이다. max-heap 상태의 이진 트리에서 pop을 하면 항상 가장 큰 값이 추출된다. min-heap의 경우는 반대로 가장 작은 값이 추출되고. 루트는 항상 max거나 min이기 때문이다. 이런 이유로 매번 min과 max를 찾아나가는 연산은 일반적인 n-size배열에선 매번 탐색에 n이 소요되고 이를 n번 반복해서 O(n^2)이다. 하지만 heap에서는 heapify에 log(n)에 소요되고 이를 n번 반복해서 O(nlogn)밖에 소요되지 않는다. 이는 아주 큰 시간 절약 효과를 가져온다.

Overall Review

참고