13주차. 해시 테이블(상위 K 빈도 요소)

31. 상위 K 빈도 요소

https://leetcode.com/problems/top-k-frequent-elements/

Top K Frequent Elements - LeetCode

📌문제

K번 이상 등장하는 요소를 추출하라(라고 알고리즘 인터뷰 책에 적혀있지만 번역 오류인 듯)

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

제일 빈도수가 높은 k번째까지 출력하라는 문제임..

 

- 예제1
  📝입력

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

  💻출력

Output: [1,2]

    
📌풀이

15ms, 45.3mb

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] answer = new int[k];
        for(int n : nums) map.put(n, map.getOrDefault(n, 0) + 1);

        List<Integer> list = new ArrayList<>(map.keySet());
        list.sort((o1, o2)->
            map.get(o2) - map.get(o1)
        );

        for(int i = 0; i < k; i++){
            answer[i] = list.get(i);
        }
        return answer;
    }
}

map의 value를 기준으로 내림차순해서 제일 높은 빈도수대로 정렬해서 풀었다.

다른 사람들 풀이를 확인해보니 우선순위 큐를 사용하는 경우가 많았다. 런타임 시간은 똑같았음.