LeetCode 347. Top K Frequent Elements 자바 문제 풀이

문제

Top K Frequent Elements - LeetCode

문제 해결 방법

• 답이 반드시 존재합니다.
• k는 n보다 작습니다.
• 일단 각 숫자의 빈도를 카운트합니다.
• 중복제외한 숫자가 얼마나 나올지 모르므로, 어레이가 아니라 해쉬맵을 사용합니다.
• 빈도순으로 정렬합니다.
• k만큼 출력합니다.

https://github.com/eunhanlee/LeetCode_347_TopKFrequentElements_Solution.git

시간복잡도: O(n log n), 공간복잡도: O(n + k)

class Solution {

    /**
     * 주어진 배열에서 가장 빈도가 높은 k개의 숫자를 찾습니다.
     *
     * @param nums 입력 숫자 배열입니다.
     * @param k 찾을 빈도가 높은 숫자의 개수입니다.
     * @return 가장 빈도가 높은 k개의 숫자를 포함한 배열입니다.
     */
    public int[] topKFrequent(int[] nums, int k) {
        // 각 숫자의 빈도를 저장하기 위한 HashMap을 생성합니다.
        HashMap<Integer, Integer> map = new HashMap<>();

        // nums 배열을 반복하며 숫자의 빈도를 업데이트합니다.
        for (int val : nums) {
            map.put(val, map.getOrDefault(val, 0) + 1);
        }

        // 맵 엔트리의 리스트를 생성하고, 빈도순으로 내림차순으로 정렬합니다.
        List<Map.Entry<Integer, Integer>> sortedEntriesList = new ArrayList<>(map.entrySet());
        sortedEntriesList.sort(Comparator.comparing(Map.Entry::getValue, Comparator.reverseOrder()));

        // 크기가 k인 결과 배열을 생성합니다.
        int[] result = new int[k];

        // 상위 k개의 빈도가 높은 숫자를 결과 배열에 채웁니다.
        for (int i = 0; i < k; i++) {
            result[i] = sortedEntriesList.get(i).getKey();
        }

        // 결과 배열을 반환합니다.
        return result;
    }
}

Follow up

• Follow up에서는 시간복잡도가 n log n 이여야 한다고 하지만, 이는 위에서 푼것과 같습니다.
• 위에서 푼 방법을 최적화 한다면, O(n log k) 로 n보다 k 가 작을경우 힙 자료구조를 사용한다면. 조금더 효율적인 알고리즘을 만들수 있습니다.
• 문제에서 주어진 조건중에 k는 n보다 작기떄문에 힙 자료구조를 사용합니다.

힙 자료구조란

• 알고리즘
  • 일단 각 숫자의 빈도를 카운트합니다.
  • 중복제외한 숫자가 얼마나 나올지 모르므로, 어레이가 아니라 해쉬맵을 사용합니다.
  • 빈도순으로 정렬을 하기위해 최댓값이나 최솟값을 빠르게 찾기위한 힙 자료구조를 사용 합니다.
  • k만큼 출력합니다.

시간복잡도: O(n log k), 공간복잡도: O(n + k)

import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        if (k == nums.length) {
            return nums; // k가 nums 배열의 길이와 같으면 모든 요소를 반환
        }

        Map<Integer, Integer> count = new HashMap<>(); // 요소의 빈도를 저장할 해시 맵
        for (int n : nums) {
            count.put(n, count.getOrDefault(n, 0) + 1); // 요소의 빈도를 계산하여 해시 맵에 저장
        }

        Queue<Integer> heap = new PriorityQueue<>((n1, n2) -> count.get(n1) - count.get(n2));
        // 최소 힙을 사용하는 우선순위 큐(heap)를 생성
        // 빈도에 따라 정렬되도록 Comparator를 설정

        for (int n : count.keySet()) {
            heap.add(n); // 요소를 힙에 추가

            if (heap.size() > k) {
                heap.poll(); // k보다 힙의 크기가 크면 가장 작은 빈도를 가진 요소 제거
            }
        }

        int[] top = new int[k]; // 결과를 저장할 배열
        for (int i = k - 1; i >= 0; --i) {
            top[i] = heap.poll(); // 힙에서 요소를 꺼내어 결과 배열에 저장 (역순으로 저장)
        }
        return top; // 결과 배열 반환
    }
}