[LeetCode] 692. Top K Frequent Words [Python] 정렬

leetcode.com/problems/top-k-frequent-words/

Top K Frequent Words - LeetCode

Given a non-empty list of words, return the k most frequent elements.

Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

Note:

1. You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
2. Input words contain only lowercase letters.

 

이 문제는 가장 빈번하게 나타나는 k개의 단어를 찾는 것이다. 노트에 나와있듯, elements의 개수는 최소 k개이므로 주어진 리스트의 엘레먼트가 k개보다 적을 경우는 걱정하지 않아도 된다. 이 문제는 sort와 hash를 이용하면 쉽게 풀수 있다.

---

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        lut = defaultdict(int)
        for i in words: lut[i] += 1
        ans = sorted(lut.keys(), key = lambda w: (-lut[w], w))
        return ans[:k]

---

해시 맵을 이용하여 리스트 안의 단어들의 출현 횟수를 찾고, 그것을 이용해 정렬을 하면 끝. 동일한 빈번도를 가지고 있을 경우 알파벳이 작은 것이 먼저 나와야 하기 때문에 sort의 컨디션은 두 개로 설정했다. 이 솔루션의 시간 복잡도는 O(n) + O(nlogn) = O(nlogn)이며 공간 복잡도는 O(n)이 나온다.