[LeetCode][JAVA] 347. Top K Frequent Elements

💡 문제

347. Top K Frequent Elements (https://leetcode.com/problems/top-k-frequent-elements/submissions/1763392089/)

자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

 

📝 선행 개념

• 빈도 집계(Frequency Count): Map<값, 빈도>로 원소별 등장 횟수 계산.
• 버킷 정렬(Bucket Sort): 빈도 f별로 리스트를 두어, 높은 빈도부터 꺼내면 Top K를 빠르게 구할 수 있음.
• 최소 힙(Min-Heap) 대안: (빈도, 값)을 크기 k의 힙으로 유지해도 됨(시간 O(n log k)).

---

🤓 문제 풀이

정수 배열 nums에서 가장 자주 등장한 원소 k개를 반환한다(순서는 무관).

• O(n)로 풀고 싶다면 버킷 정렬이 깔끔하다:
  1. 해시맵으로 빈도 계산 →
  2. 빈도 값(최대 n)을 인덱스로 갖는 버킷 배열에 값들을 쌓음 →
  3. 큰 빈도부터 역순 스캔하며 k개를 채우면 종료.

🔨 문제 설명

• 입력: 정수 배열 nums, 정수 k
• 출력: 가장 빈번한 k개의 원소 (순서 상관 없음)

예)

• nums=[1,1,1,2,2,3], k=2 → [1,2]
• nums=[1], k=1 → [1]
• nums=[1,2,1,2,1,2,3,1,3,2], k=2 → [1,2](예시 중 하나)

제약

• 1 <= nums.length <= 1e5, -1e4 <= nums[i] <= 1e4
• k는 [1, 고유 원소 수] 범위

---

🔨 접근 방법

1. 빈도 집계: Map<Integer, Integer> freq 생성.
2. 버킷 구성: List<Integer>[] buckets = new List[n+1]
   • 인덱스 f에 빈도가 f인 값들을 보관.
3. 역순 스캔: f = n..1로 내려가며 버킷에서 값을 꺼내 k개 채우면 종료.

버킷의 최대 인덱스는 배열 길이 n(동일 값이 전부일 때 빈도 최대).

---

🔨 문제 풀이 과정

 

• nums 한 번 순회 → 빈도 O(n)
• freq.entrySet() 순회 → 버킷에 분배 O(고유원소)
• 버킷을 높은 빈도부터 훑으며 채움 → 최악 O(n)

 

 

---

🔨 구현코드

package leetcode;

import java.util.*;

/**
 * 347. Top K Frequent Elements
 * - 빈도 집계 + 버킷 정렬
 * - 시간복잡도 O(n), 공간복잡도 O(n)
 */
public class LeSolution06 {
    public int[] topKFrequent(int[] nums, int k) {
        // 1) 빈도 집계
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : nums) {
            freq.put(x, freq.getOrDefault(x, 0) + 1);
        }

        // 2) 버킷 구성 (빈도 = 인덱스)
        @SuppressWarnings("unchecked")
        List<Integer>[] buckets = (List<Integer>[]) new List[nums.length + 1];
        for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
            int f = e.getValue();
            if (buckets[f] == null) buckets[f] = new ArrayList<>();
            buckets[f].add(e.getKey());
        }

        // 3) 높은 빈도부터 k개 수집
        int[] ans = new int[k];
        int idx = 0;
        for (int f = buckets.length - 1; f >= 1 && idx < k; f--) {
            if (buckets[f] == null) continue;
            for (int val : buckets[f]) {
                ans[idx++] = val;
                if (idx == k) break;
            }
        }
        return ans;
    }

    // (보너스) 최소 힙 버전: O(n log k)
    public int[] topKFrequentHeap(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : nums) freq.put(x, freq.getOrDefault(x, 0) + 1);

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0])); // [freq, val]
        for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
            pq.offer(new int[]{e.getValue(), e.getKey()});
            if (pq.size() > k) pq.poll();
        }

        int[] ans = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            ans[i] = pq.poll()[1];
        }
        return ans;
    }

    public static void main(String[] args) {
        LeSolution06 sol = new LeSolution06();
        System.out.println(Arrays.toString(sol.topKFrequent(new int[]{1, 2, 3, 4, 5}, 2)));
        System.out.println(Arrays.toString(sol.topKFrequent(new int[]{1,1,1,2,2,3}, 2)));
        System.out.println(Arrays.toString(sol.topKFrequent(new int[]{1}, 1)));
        System.out.println(Arrays.toString(sol.topKFrequent(new int[]{1,2,1,2,1,2,3,1,3,2}, 2)));
    }
}

---

📚 풀이 보완

코드 설명 (핵심 라인)

• buckets[f].add(e.getKey())
  → 빈도가 f인 값들을 동일 버킷에 모은다.
• 역순 스캔 시 idx == k에서 즉시 종료
  → 필요 이상 순회 방지.
• System.out.println(int[])를 그대로 출력 → 참조값이 출력됨
  → Arrays.toString(...)으로 포매팅.
• 버킷 배열 제네릭 경고 → 캐스팅 + @SuppressWarnings("unchecked")로 정리.
• k가 고유 원소 수와 같을 때도 로직이 동일하게 동작해야 함(문제 보장 사항).

---

📍 Plus+

언제 힙을 선택할까?

• k가 매우 작고 n이 큰 경우 → 힙(O(n log k))이 메모리/캐시 측면에서 유리할 때가 있음.
• 반대로 일반적 코딩 인터뷰/LeetCode에선 버킷이 가장 단순·빠름.

안정성/재현성

• 출력 순서가 임의여도 허용(문제 조건).정렬이 필요하다면 마지막에 결과를 정렬하면 됨(추가 O(k log k)).

시간 복잡도와 공간 복잡도 분석

 

시간 복잡도

공간 복잡도

요약

시간 복잡도: O(n)

• 빈도 집계 O(n) + 버킷 분배 O(고유원소) + 버킷 역순 스캔 O(n)

공간 복잡도: O(n)

• 해시맵(고유원소 수) + 버킷 총합 원소 수 n

 

• 핵심 전략: Map으로 빈도 집계 → 버킷 정렬로 높은 빈도부터 채우기
• 장점: 직관적, 빠름(O(n)), 구현 간결
• 대안: k가 매우 작으면 최소 힙도 실용적

 

 

---

풀이 참고 로직

 

• freq.put(x, freq.getOrDefault(x, 0) + 1);
• buckets[f].add(value); (빈도→인덱스 매핑)
• 역순 스캔: for (int f = n; f >= 1 && idx < k; f--) ...