[leetcode] Top K Frequent Elements

리트코드 문제: Top K Frequent Elements

이 문제는 배열에서 자주 등장하는 k개의 요소를 찾는 문제입니다. 예를 들어, 배열 [1,1,1,2,2,3]과 k = 2가 주어진다면, 가장 빈번하게 등장한 숫자는 1과 2이므로 [1, 2]가 답이 됩니다.

---

문제 분석

이 문제는 배열의 각 요소가 몇 번 등장하는지를 계산하고, 그중에서 자주 등장한 k개의 요소를 추출하는 문제입니다.

---

풀이 접근

1. 빈도 계산
   먼저 배열에서 각 숫자가 몇 번 등장했는지를 파악해야 합니다. 이를 위해 **해시맵(Map)**을 사용해 각 숫자의 빈도를 기록할 수 있습니다.
2. 빈도별 정렬
   각 숫자의 등장 횟수를 기준으로 배열을 정렬한 후, 그중에서 가장 빈번하게 등장한 k개의 요소를 추출하면 됩니다.

---

코드 설명

var topKFrequent = function(nums, k) {
    const numsMap = new Map();
    
    // 각 숫자의 빈도를 해시맵에 저장
    nums.forEach((num) => {
      numsMap.set(num, numsMap.has(num) ? numsMap.get(num) + 1 : 1);
    });

    const numAndCountArray = [];
    // 해시맵의 키(숫자)와 값(빈도)을 배열로 변환
    numsMap.forEach((value, key) => numAndCountArray.push([key, value]));

    // 빈도를 기준으로 내림차순 정렬
    const result = numAndCountArray.sort((a, b) => b[1] - a[1]);

    // 상위 k개의 숫자 반환
    return result.slice(0, k).map(([num, _]) => num);
};

코드 동작 방식:

1. 해시맵으로 빈도 계산
   numsMap은 각 숫자(num)가 몇 번 등장했는지를 기록합니다. 만약 이미 해당 숫자가 해시맵에 존재하면 그 값을 1 증가시키고, 그렇지 않으면 새로 추가합니다.
2. 해시맵을 배열로 변환
   numAndCountArray 배열은 각 숫자와 그 빈도를 저장한 배열입니다. [숫자, 빈도]의 형태로 각 항목을 담습니다.
3. 빈도별 정렬
   sort 함수를 사용해 빈도를 기준으로 내림차순으로 정렬합니다. 즉, 가장 많이 등장한 숫자가 배열의 앞쪽에 오도록 정렬합니다.
4. 상위 k개의 요소 추출
   정렬된 배열에서 상위 k개의 요소를 추출하고, 그 숫자만을 반환합니다.

---

시간 복잡도 분석

• 해시맵을 채우는 과정: 배열을 한 번 순회하므로 O(n).
• 정렬 과정: 정렬은 일반적으로 O(n log n).
• 최종적으로 **O(n log n)**의 시간 복잡도를 갖습니다.

---

성능 결과

• 실행 시간: 56ms (94.33% 보다 빠름)
• 메모리 사용량: 52.04MB (92.56% 보다 적음)

---

이 코드는 간결하면서도 효율적으로 문제를 해결할 수 있는 방법을 제시합니다. 더 나은 성능을 원한다면 bucket sort 또는 heap을 사용해 정렬 단계를 최적화할 수 있습니다.