[리트코드] Top K Frequent Elements(python)

리트코드, Top K Frequent Elements_K개의 자주 나온 원소들

TL;DR

• 딕셔너리(dictionary)를 활용하여 문제를 해결할 수 있는지
• `collections.Counter`를 활용할 수 있는지

문제 분석

1. 정수 배열 nums와 정수 k가 주어질 때, 상위 k개의 가장 자주 등장한 원소를 반환하라.
2. 반환되는 정답은 어떤 순서로 정렬되어도 상관없다.

 

- 1 : 해결해야 하는 문제에 대해서 설명해야 한다.

- 2 : 자주 등장한 k개의 숫자들을 별도의 정렬 없이 그냥 반환하면 된다. 만약 이 부분에 다른 조건이 명시된다면 해당 조건을 반영하여 답을 반환해야 한다.

입출력 형태

입출력 예시

 

- 주어진 숫자 배열은 3개의 1, 2개의 2, 1개의 3으로 이루어져 있다.

- k가 2로 주어졌으므로 가장 자주 등장한 2개의 원소, 즉 1과 2를 반환해야 한다.

풀이

1. dictionary를 활용하여 해결하는 방법

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        counter = collections.defaultdict()
        for num in nums:
            if num in counter:
                counter[num] += 1
            else:
                counter[num] = 1
                
        return [num for (num, _) in sorted(counter.items(), key=lambda item: item[1], reverse=True)[:k]]

 

- 숫자 배열에 있는 숫자를 key로, 등장한 횟수를 value로 하는 dictionary를 사용하는 풀이 방법이다.

- `dict()` 또는  `{}`와 같은 기본 딕셔너리를 사용할 경우 존재하지 않는 key에 대한 별도의 처리를 해주어야 하므로, `collections.defaultdict()`를 사용한다.

- 배열을 순회하며, 각 숫자의 숫자를 딕셔너리에 저장한다.

- 저장된 딕셔너리의 value 순으로 정렬하여, 상위 k개를 반환한다.

    - `key=lambda item: item[1]` : item은 딕셔너리의 각 원소를 나타낸다. value로 정렬하고 싶기 때문에 1번 인덱스를 적었다.

    - `reverse=True` : 오름차순 정렬이 되는데, 많이 등장하는 원소를 알고 싶으므로, 역순 정렬 옵션을 지정한다.

- 정렬된 딕셔너리에서 value 말고 key만 필요하므로 key만 배열에 담아 반환한다.

 

2. collections.Counter를 활용하여 해결하는 방법

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        counter = collections.Counter(nums)
        
        return [num for (num, _) in counter.most_common(k)]

 

- collections.Counter는 iterable한 객체의 원소의 숫자를 세서 돌려주는 기능을 제공한다.

- 또한 most_common을 통해 원하는 숫자만큼의 상위 원소를 반환한다.

- 1번의 방법에 비해 훨씬 간단하게 문제를 해결할 수 있다.