- 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'}
