99클럽 코테 스터디 10일차 TIL

오늘의 문제

LeetCode 347: Top K Frequent Elements
LeetCOde 2283: Check if Number Has Equal Digit Count and Digit Value

문제 요약

Top K Frequent Elements

• nums 배열에서 가장 많이 등장한 k개의 숫자 return (배열로)
• 시간복잡도 O(nlogn)

풀이 전략

시간복잡도 O(nlogn) 이라, brute-force는 불가능

• Counter 함수와 Heap을 사용해서 풀이
• Counter 함수: 주어진 배열에서의 빈도수를 dictionary 형태로 생성 -> 시간복잡도 O(n)
• Heap: 빈도 높은 k개를 추출하기 위해 사용 -> 시간복잡도 O(nlogn)

코드

from collections import Counter
import heapq 

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count_dict = Counter(nums)
        return heapq.nlargest(k, count_dict.keys(), key=count_dict.get)

• heapq.nlargest(): 빈도 높은 k개의 요소 추출
• count_dict.keys() 키값을 기준으로 iterate
• count_dict.get (=value, 즉 빈도수) 를 비교 기준으로 삼아서 k개 추출

고민

함수만 사용해서 구현한것같은데 이게 맞나 싶음
직접 구현한 내용도 추가해보자