LeetCode [347]: Top K Frequent Elements

📌 LeetCode [347]: Top K Frequent Elements

🔗 문제 링크

---

문제 설명 📄

주어진 정수 배열 nums와 정수 k가 주어질 때, 가장 빈도수가 높은 k개의 요소를 반환하는 문제입니다. 반환된 요소는 어떤 순서로든 상관없습니다.

---

문제 접근 방식 📋

먼저, 정수 배열에서 각 숫자의 빈도수를 세는 것이 문제 해결의 핵심이라고 생각했습니다. 이를 위해 딕셔너리를 사용하여 각 숫자의 빈도수를 저장한 후, 빈도수를 기준으로 내림차순 정렬하여 상위 k개의 요소를 추출하는 방식으로 접근했습니다.

아이디어 설명 💡

1. 딕셔너리(pattern)를 사용하여 각 숫자의 빈도수를 계산합니다.
2. pattern.items()를 빈도수 기준으로 내림차순 정렬하여 sortedItems 리스트를 만듭니다.
3. 상위 k개의 요소를 추출하여 answer 리스트에 추가하고, 이를 반환합니다.

---

Solution 💻

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        pattern = dict()

        for n in nums:
            if n not in pattern:
                pattern[n] = 0
            pattern[n] += 1

        sortedItems = sorted(pattern.items(), key=lambda x: x[1], reverse=True)

        answer = []
        for i in range(k):
            answer.append(sortedItems[i][0])
        return answer

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n log n)
  • n은 배열 nums의 길이입니다.
  • 숫자의 빈도수를 계산하는 데 O(n)이 걸리고, 정렬하는 데 O(n log n)이 걸립니다.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(n)
  • 딕셔너리와 정렬된 리스트에 저장된 요소들이 추가적인 공간을 차지합니다.

---

리팩토링 🛠️

개선된 코드 (Counter와 heapq 사용)

from collections import Counter
import heapq

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = Counter(nums)
        return [item for item, _ in heapq.nlargest(k, count.items(), key=lambda x: x[1])]

리팩토링 후 시간 복잡도 분석 ⏲️

• 시간 복잡도: O(N + K log K)
  • Counter(nums) 를 사용하여 빈도수를 계산하는데 O(N)가 걸립니다.
  • heapq.nlargest를 사용하여 상위 k개의 요소를 추출하는 데 O(k log k)가 걸립니다.
• 공간 복잡도: O(n)
  • 딕셔너리와 힙에 저장된 요소들이 추가적인 공간을 차지합니다.