[99클럽 코테 스터디 1일차 TIL] Top K Frequent Elements

오늘의 학습 키워드 

- Priority Queue

- Sort()

 

문제 

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

 

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

 

Constraints:

 

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

Follow up: Your algori thm's time complexity must be better than O(n log n), where n is the array's size.

풀이 과정  

 입력 : nums 정수 배열, int k = 가장 빈번한 순위 k번째 까지

로직 : 숫자가 나올때마다 카운팅을 하고 최종적으로 그 카운트가 높은 순서대로 k번째까지 출력 

공통  : HashMap을 사용해서 Counting 연산 O(1) n번 -> O(n)

 

1. 정렬 방식 

sort() -> O(nlongn)

순서대로 선택 -> O(k)

 

최종  :  O(nlongn)

 

2. 우선순위 큐 (min - heap)

 

반복문을 통해서 priorityQueue add 연산 -> O(logk) -> N번 반복 O(nlogK)

결과 반환(poll())은 O(KlogK)

 

최종  :  O(nlongn)

 

- 답은 유일 무이하다. -> K번쨰 해당하는 빈번도 숫자 중복이 없다. 

- 출력 : int 리스트 형태로 반환 

 

 

1. 정렬 방식 

import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 1. 숫자별 등장 횟수 카운팅
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // 2. 리스트로 변환 후 등장 횟수를 기준으로 정렬
        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
        list.sort((a, b) -> b.getValue() - a.getValue()); // 빈도수가 높은 순으로 정렬

        // 3. 상위 k개의 키만 선택하여 배열로 변환
        int[] answer = new int[k];
        for (int i = 0; i < k; i++) {
            answer[i] = list.get(i).getKey();
        }

        return answer;
    }
}

 

2. 우선순위 큐 

import java.util.*;


class Solution {
    public int[] topKFrequent(int[] nums, int k) {

        // 1. 숫자별 카운팅 
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int num : nums){
            map.put(num, map.getOrDefault(num,0) +1);
        }
        // 2. 빈도가 높은 K 개 요소 만 남기고 버리기 
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(Comparator.comparingInt(map::get));
        // key : number value : count 
        for (int key : map.keySet()){
            minHeap.add(key);
            if (minHeap.size() > k){
                minHeap.poll(); // -> 현재 반복에서 가장 작은 빈도수를 가진 숫자가 빠져나감. 
            }
        }

        // 3. 출력 
        int[] answer = new int[k];
        for (int i=k-1; i>=0; i--){
            answer[i] = minHeap.poll();
        }
        return answer;
    }
}

 

 

2025 팀네이버 공채를 풀면서 priorityQueue에  map을 적용하는 법을 몰랐었는데 덕분이 이제야 방법을 알아간드아...