[파이썬 알고리즘] 상위 K 빈도 요소

문제 파악 

상위 k번 이상 등장하는 요소를 추출해라 예를들어,

k = 2 이면 output [1, 2]가 나오고, k = 3이면 [1 , 2 ,3] 이 나온다.

 

문제풀이 1) Counter를 이용한 음수 순 추출

 

- 요소의 값을 키로 하는 해시 테이블을 만들고 여기에 빈도 수를 저장한 다음, 우선순위 큐를 이용해 상위 k번 만큼 추출하면 k번 이상 등장하는 요소를 손쉽게 추출 할 수 있다.

- 파이썬에서 우선순위 큐는 힙을 활용하는 heqpq 모듈을 사용한다.

최소 힙: 부모의 노드의 키 값이 자식의 노드 키 값 작거나 같은 완전 이진트리

# 요소의 값을 키로 하는 해시 테이블을 만들고 여기에 빈도 수를 저장한 다음,
# 우선순위 큐를 이용해 상위 k번만큼 추출하면 k번 이상 등장하는 요소를 손쉽게 추출할 수 있다.

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    freqs = collections.Counter(nums)
    # [1,1,1,2,2,3] -> counter({1: 3, 2: 2, 3: 1})

    freqs_heap = []

    # heappush()로 삽입하게 되면 매번 heapify()가 일어나기 때문에 별도로 처리 필요가 없어진다.
    # heapify란 주어진 데이터를 힙 성질을 만족하도록 만드는 것
    # 힙에 음수로 삽입 (이유: heqpq 모듈은 최소 힙(Min-Heap)만 지원하기 때문)
    # -> 최소 힙을 그대로 사용하되 음수로 변환해 가장 빈도 수가 높은 값이 가장 큰 음수가 되게 한다.
    for f in freqs:
        heapq.heappush(freqs_heap, (-freqs[f], f))

    topk = list()
    # k 만큼 추출, 최소 힙(Min Heap)이므로 가장 작은 음수 순으로 추출
    for _ in range(k):
        topk.append(heapq.heappop(freqs_heap)[1])

    return topk

 

 

문제 풀이 2) 파이썬 다운 방식

def topKFrequent(self, nums, k):
    return list(zip(*collections.Counter(nums).most_common(k)))[0]

 

1. collections. Counter(nums) 를 통하여 주어진 nums list를 Counter 객체로 변환한다.

> nums = [1, 1, 1, 2, 2, 3], k = 2 -> counter = [(1, 3), (2, 3), (3, 1)]

 

2. most_common(k) 메소드를 활용해 가장 빈번한 k개의 요소를 추출

> collections.Counter(nums).most_common(k) = [(1, 3), (2, 3)]

 

3. *(unpack)를 통해 리스트를 풀어준다.

> *collections.Counter(nums).most_common(k) = [[1, 3], [2, 3]]

 

4. 현재 리스트는 [수, 빈도]로 저장되어 있기에, zip을 통해 필요한 정보인 '수'만 검출하고 (tuple 형태로 반환됨),

   리스트로 리턴해야 하므로 list()로 묶어준다.

> list(zip(*collections.Counter(nums).most_common(k)))[0] = (1, 2)

 

 

파이썬 함수)

most_common()

-> 빈도 수가 높은 순서대로 아이템을 추출하는 기능

 

zip()

-> 2개 이상의 시퀀스를 짧은 길이를 기준으로 일대일 대응하는 새로운 튜플 시퀀스를 만드는 역할을 한다.

 

>>> a = [1, 2, 3, 4, 5]

>>> b = [2, 3, 4, 5]

>>> c = [3, 4, 5]

>>> list(zip(a, b))

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

>>> list(zip(a, b, c))

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

 

아스테리스크( * )

-> 주로 튜플이나 리스트를 언패킹하는 데(풀어 헤치는 데) 사용한다.

>>> fruits = ['lemon', 'pear', 'watermelon', 'tomato']

>>> print(*fruits)

lemon pear watermelon tomato