31. Top K Frequent Elements

아현·2021년 4월 9일
0

Algorithm

목록 보기
32/400

리트코드


  • k번 이상 등장하는 요소를 추출하라



1. Counter를 이용한 음수 순 추출 (108 ms)



class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freqs = collections.Counter(nums)
        freqs_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
        


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

  • 먼저 빈도수는 collections.Counter를 이용해서 구현한다.

    • 입력값이 [1,1,1,2,2,3]일 때 freqs의 결과는 다음과 같다
    Counter({
        1: 3,
        2: 2,
        3: 1
    })
  • 이제 힙에 삽입해보자. 삽입 방식은 2가지가 있다.

    1) 일반적인 파이선 리스트에 모두 삽입한 다음 마지막에 heapify( )를 하는 방식

    2) 매번 heappush()를 하는 방식

    • heappush()로 삽입하게 되면 매번 heapify()가 발생하기 때문에 별도로 처리할 필요가 없다.
    • 원래 이 방식이 힙의 삽입 방식이기도 하다.
  • 여기서는 빈도 수를 키로하고, freqs의 키를 값으로 했다.

    • 즉, 키와 값을 바꿔서 힙에 추가 했다.

    • 힙은 키 순서대로 정렬되기 때문에 이를 위해 빈도 수를 키로 한 것이다.

  • 값을 음수로 저장했다.

    • 파이썬 heapq 모듈최소 힙(Min-heap) 만 지원하기 때문이다.

    • 모듈 차원에서는 최대 힙(Max-heap)도 지원하긴 하지만 메소드가 프로텍티드 멤버(Protected Member)로 선언되어 있고 함수명이 밑줄(_)로 시작하기 때문에 직접 호출하는 게 권장하는 방법은 아니다.

    • 따라서, 여기서는 최소 힙을 그대로 사용하되 음수로 변환해 가장 빈도 수가 높았던 값을 추출할 수 있다.

  • 마지막으로 다음과 같이 heappop()으로 k번만큼 값을 추출하면 결과를 얻을 수 있다.



2. 파이썬다운 방식 (104 ms)



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

  • 힙에 넣고 빼는 작업을 자동으로 진행하는 법은 없을까?

  • 파이썬의 Counter에는 most_common() 이라는 빈도 수가 높은 순서대로 아이템을 추출하는 기능을 제공한다.


>>> collections.Counter(nums).most_common(k)
[(1,3), (2,2)]
  • 이제 여기서 1과 2를 추출해 내기만 하면 된다.

    • 여기서는 파이썬의 zip()*(별표)를 활용한다.



✔ zip( ) 함수


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

    • 파이썬 3+부터는 제너레이터를 리턴한다 (2까지는 리스트를 리턴)
    • list( )로 변환이 필요하다.
  • zip( )결과 자체는 튜플 시퀀스를 만들기 때문에 불변(immutable) 객체다.

  • zip( )은 여러 시퀀스에서 동일한 인덱스 아이템을 순서대로 추출하여 튜플로 만들어주는 역할을 한다.

>>> a = [1, 2, 3, 4, 5]
>>> b = [2, 3, 4, 5]
>>> c = [3, 4, 5]
>>> zip(a,b)
<zip object at 0x10d30480>

>>> 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)]



✔ 아스테리스크( * )


  • 파이썬에서 *언팩(Unpack) 이다.

    • 즉, 시퀀스 언패킹 연산자(Sequence Unpacking Operator)로 말 그대로 시퀀스를 풀어 헤치는 연산자를 뜻한다.

    • 주로 튜플이나 리스트를 언패킹하는 데 사용한다.



#언패킹

>>> list(zip(*collections.Counter(nums).most_common(k)))

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



#언패킹 안했을 때

>>> list(zip(collections.Counter(nums).most_common(k)))

[(1,3),), ((2,2),)]
  • zip( )을 통해 묶은 결과를 보면 튜플이 풀어지지 않고 그대로 하나의 값처럼 묶여버렸다. 이 경우 *로 언패킹을 해줘야 튜플의 값을 풀어 해칠 수 있다.

  • 파라미터가 되었을 때는 반대로 패킹(Packing)도 가능하다.

>>> print(*fruits)

~~~

>>> def f(*params):
...    print(params)

>>> f('a','b','c')

('a', 'b', 'c')
  • zip( )에 파라미터를 여러 개 쓸 수 있다는 얘기 또한 내부적으로 zip( )함수 정의에서 *로 패킹하고 있다는 얘기기도 하다.

    • 이처럼 하나의 파라미터를 받는 함수에 3개의 파라미터를 전달했지만, params 변수 하나로 패킹되어 처리된다.

    • 이는 파이썬 3+에서 print( ) 함수가 처리되는 기본 동작 원리이기도 하다.


  • ** 2개는 키/값을 언패킹하는 데 사용된다.
 >>> date_info = {'year': '2020', 'month': '01', 'day': '7'}
 >>> new_info  = {**date_info, 'day': '14'}
 >> new_info
 {'year': '2020', 'month': '01', 'day': '14'}
 
 
profile
For the sake of someone who studies computer science

0개의 댓글