ch11-4(leetcode 347). 상위 K 빈도 요소

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

leetcode 347번 ( https://leetcode.com/problems/top-k-frequent-elements/ )

 

풀이 1. 

collections 라이브러리의 Counter 자료형에서 기본으로 주어지는 메소드만으로도 풀 수 있다. 

 

Counter 객체를 초기화할 때 매개변수로 문자열이나 리스트를 넣을 수 있다. Counter 클래스는 딕셔너리의 하위 클래스라서 딕셔너리의 기본 기능들은 다 가지고 있다. 다만 문자열의 문자나 리스트의 개별 원소를 key 값으로, 해당 문자나 원소의 등장 빈도를 value로 갖는다. 

counter = collections.Counter(nums)	# initialize Counter object

 

Counter 클래스의 most_common(k) 메소드를 사용하면 Counter에 저장된 key-value pair 중 가장 등장빈도(value)가 높은 쌍을 총 k개 리턴한다. 

리스트 형태로 리턴하고, 리스트의 각 원소는 (key, value)로 된 튜플(tuple) 형식이다. 

return counter.most_common(k)
# [(1,4), (2,3)] (when 1 appeared 4 and 2 appeared 3 times)

 

list comprehension을 통해서 이 튜플-리스트를 key만 들어있는 리스트 형태로 바꿔 주면 된다. 

(key는 튜플의 0번째 인덱스이다.)

 

전체 코드는 다음과 같다. 

class Solution(object):
	def topKFrequent(self, nums, k):
		counter = collections.Counter(nums)
		return [mc[0] for mc in counter.most_common(k)]

 

풀이 2. 

풀이 1번에서 맨 마지막에 for loop로 리스트 컴프리헨션을 사용하지 않고, zip()을 사용해서 더 간단히 풀 수 있다고 한다. 

zip() 함수는 여러 개의 리스트를 병렬적으로 묶어 준다. 

nums = [1,2,3]
alphabets = ["a","b","c"]

for z in zip(nums, alphabets):
	print(z)
    
# [1, "a"]
# [2, "b"]
# [3, "c"]

 

풀이 1번의 코드를 이렇게 바꿀 수 있다. 

class Solution(object):

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

 

풀이 3. 

Counter 변수는 리스트의 값과 발생빈도를 저장하는 용도로만 사용하고, 힙에다가 Counter에 있는 값들을 저장 및 정렬해서 하나씩 총 k개를 빼는 방법도 있다. 힙을 사용할 때는 priority-queue와 heapq 라이브러리 등 여러 라이브러리가 있지만 thread-safe로 인한 locking 오버헤드 문제 때문에 여기서는 heapq 라이브러리를 사용한다. 

 

힙에 counter의 원소들(key-value 한 쌍)을 넣을 때는 heappush() 메소드를 사용한다. 

heapq.heappush(heap 변수, heap 변수에 넣을 값)

 

값을 넣을 때는 counter 객체에서 자동으로 계산해 준 등장 빈도(value)를 음수로 바꿔서 넣는다. heapq는 min heap만 제공하기 때문이다. 

(정확히는 max heap도 제공하지만 해당 메소드는 protected 메소드라서 직접 접근하는 것은 권장하지 않는다.)

 

힙에 저장된 원소들을 제거할 때는 heappop() 메소드를 사용한다. 매개변수를 받지 않으며, heap에 저장된 값을 정렬한 뒤 가장 작은 원소부터 리턴한다. 

heapq.heappop()

 

이후 heappop()으로 힙에서 정렬된 원소들을 총 k번 빼 주고, heappop()을 통해 힙에서 제거되어 반환된 key-value 쌍은 리스트에 저장해 주자. 

 

참고한 포스트

https://docs.python.org/3/library/collections.html