[LEETCODE] 347: Top K Frequent Elements(Python)

Top K Frequent Elements - LeetCode

문제 설명

리스트가 주어질 때 k번째로 빈도가 높은 원소들을 출력해 보자.

만약 리스트가 [1,1,1,2,2,3,3,3]이고 k=2라면, 원소별 빈도가 1:3, 2:2, 3:3이므로 오름차순 나열하면 1,3,2이다. k가 2이므로 정답은 [1,3]이 된다.

나의 풀이

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        frequency=dict()
        for i in nums:
            frequency[i]=frequency.get(i,0)+1
        
        d=dict()
        for i in frequency.items():
            d[i[1]]=d.get(i[1],[])+[i[0]]
        
        answer=[]
        for i in range(10000,0,-1):
            if i in d:
                answer+=d[i]
        
        return answer[:k]

먼저 리스트의 원소별 빈도를 frequency 딕셔너리에 넣었다.

리스트가 [1,1,1,2,2,3,4,4,4], k=3일 때 frequency={1:3, 2:2, 3:1, 4:3}이다.

다음으로는 해당 빈도수를 가지는 원소를 다시 딕셔너리에 넣었다. 즉 frequency 딕셔너리의 키:밸류 값을 밸류:키 값으로 변환한다. 빈도수는 중복될 수 있으므로 단순히 반전하지 말고 밸류값을 리스트 형식으로 작성했다.

즉 d={3:[1,4], 2:[2], 1:[3]}이다.

리스트의 길이는 최대 10^5이고, 모든 원소가 동일할 때 최대 빈도수인 10^5를 가진다. 정렬하지 않고 문제를 풀어야 하기 때문에, d에서 빈도수가 큰 값부터 찾아내서 answer 리스트에 삽입한다.

answer 리스트에는 빈도수가 높은 원소들 순으로 들어가 있기 때문에 k번째 원소까지 출력하면 된다.

시간복잡도

frequency를 만들 때 O(n), d를 만들 때 O(n), answer 리스트를 만들 때 O(n), k번째 원소까지 출력할 때 O(n)이 걸린다. 따라서 전체 시간복잡도는 O(n)이다.