99클럽 코테 스터디 30일차 TIL/ Top K Frequent Elements

Top K Frequent Elements

학습 키워드: 정렬, 카운터, 리스트 컴프리헨션
문제 링크: https://leetcode.com/problems/top-k-frequent-elements/description/

문제 설명

정수 배열 nums와 정수 k가 주어졌을 때, 가장 빈번하게 나타나는 k개의 요소를 반환하세요. 반환되는 요소들은 어떤 순서로든 상관없습니다.

제한 조건

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

문제 풀이

from collections import Counter

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnt_dict=Counter(nums)
        a = sorted(cnt_dict.items(),key=lambda x:-x[1])
        return [item[0] for item in a[:k]]

코멘트

문제에서 추가 적으로 요구하는 것은 O(nlogn)의 시간 복잡도로 풀기 였는데 counter로 셀 때 n, 정렬할 때 nlogn의 시간 복잡도가 걸리기 때문에 의도한 대로 풀었다고 생각한다. 다만, value의 개수가 같을 때는 어떨지 고민이 되었는데 answer is unique라는 설명으로 보아 개수가 다 다르다고 가정하는 것 같았다.