99클럽 코테 스터디 1일차 TIL - 가장 빈도가 높은 k개의 요소 찾기

가장 빈도가 높은 k개의 요소 찾기

문제: https://leetcode.com/problems/top-k-frequent-elements/description/
알고리즘 분류:
Array Hash Table Divide and Conquer Sorting Heap (Priority Queue)
Bucket Sort Counting Quickselect

접근방법

• 빈도수 계산
  • Map을 사용 ➡️ 각 숫자가 배열에서 몇 번 등장하는지 계산
• 버킷 정렬
  • 문제의 요구사항에 따라 O(n log n)보다 빠른 시간 복잡도가 필요
  • 버킷 정렬 시간 복잡도 : O(n)
• 결과 추출
  • 가장 높은 빈도수를 가진 버킷부터 시작 ➡️ k개의 요소를 결과 배열에 추가

내 코드

function topKFrequent(nums, k) {
    // 각 숫자의 빈도수를 저장할 Map 생성
    const frequencyMap = new Map();
    
    // 모든 숫자의 빈도수 계산
    for (const num of nums) {
        frequencyMap.set(num, (frequencyMap.get(num) || 0) + 1);
    }
    
    // 빈도수를 기준으로 내림차순 정렬된 배열 생성
    // 시간 복잡도는 O(n log n)이 아닌 O(n)을 달성하기 위해 버킷 정렬 사용
    const buckets = Array(nums.length + 1).fill().map(() => []);
    
    // 각 숫자를 빈도수에 해당하는 버킷에 넣기
    for (const [num, freq] of frequencyMap) {
        buckets[freq].push(num);
    }
    
    // 결과 배열
    const result = [];
    
    // 가장 높은 빈도수부터 시작하여 k개의 요소를 결과 배열에 추가
    for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
        if (buckets[i].length > 0) {
            result.push(...buckets[i].slice(0, k - result.length));
        }
    }
    
    return result;
}