[LeetCode] 347. Top K Frequent Elements - Java

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

Top K Frequent Elements - LeetCode

---

문제

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 algorithm's time complexity must be better than O(n log n), where n is the array's size.

---

풀이

풀이 과정

배열의 각 요소마다 사용된 개수를 map으로 저장하여 많이 나온 순서대로 k만큼 뽑아 결과로 return하도록 풀이한다.

우선 최종 정답을 return할 길이 k만큼의 배열을 하나 선언한다.

// 최종 return할 결과 배열
int[] answer = new int[k];

 

만약 nums 배열의 길이가 k와 같다면 배열의 요소가 한번씩 사용된 한가지 경우밖에 존재하지 않으므로 바로 nums 배열을 return 한다.

// 배열의 숫자의 개수와 k값이 같다면 nums자체가 정답이 됨
if(nums.length == k) return nums;

 

num배열의 각 요소의 개수를 저장할 map을 선언하고 반복문을 통해 개수를 카운트하여 map에 저장한다.

Map<Integer, Integer> countMap = new HashMap<>();
// num배열의 각 요소의 개수를 세며 map에 저장
for(int i : nums) {
    countMap.put(i, countMap.getOrDefault(i, 0) + 1);
}

 

다음으로 가장 많이 사용된 요소부터 k개만큼 추출해야 하는데 우선순위큐를 이용하여 이 방법을 구현한다.
nums 배열의 각 요소와 그 개수가 저장되어있는 countMap에서 두 번째 요소, 즉 각 요소의 개수를 기준으로 정렬하는 우선순위큐를 선언한다.

// 우선순위큐 생성
// countMap의 두 번째 요소 = 각 요소의 개수를 기준으로 정렬
PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> countMap.get(o1) - countMap.get(o2));

 

nums 배열의 모든 요소값들을 순회하며 큐에 삽입한다. 이 때 필요한 요소의 개수는 k만큼이므로 만약 큐의 사이즈가 k를 넘어가는 경우 마지막 요소( = 우선순위가 가장 낮은 요소 = 제일 적게 사용된 요소 )를 제거한다

// nums 배열의 모든 요소 값들을 큐에 삽입
for(int i : countMap.keySet()) {
    pq.add(i);
    // 큐의 길이가 k보다 커지는 경우 마지막 요소를 제거
    if(pq.size() > k) pq.poll();
}

 

큐의 값을 차례대로 뽑아 결과 배열에 저장하여 최종 return한다.

// 큐의 값을 차례대로 결과 배열에 저장하여 return
for(int i = 0; i < k; i++) {
    answer[i] = pq.poll();
}

return answer;

---

최종 코드

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 최종 return할 결과 배열
        int[] answer = new int[k];
        
        // 배열의 숫자의 개수와 k값이 같다면 nums자체가 정답이 됨
        if(nums.length == k) return nums;
        
        Map<Integer, Integer> countMap = new HashMap<>();
        // num배열의 각 요소의 개수를 세며 map에 저장
        for(int i : nums) {
            countMap.put(i, countMap.getOrDefault(i, 0) + 1);
        }
        
        // 우선순위큐 생성
        // countMap의 두 번째 요소 = 각 요소의 개수를 기준으로 정렬
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> countMap.get(o1) - countMap.get(o2));
        // nums 배열의 모든 요소 값들을 큐에 삽입
        for(int i : countMap.keySet()) {
            pq.add(i);
            // 큐의 길이가 k보다 커지는 경우 마지막 요소를 제거
            if(pq.size() > k) pq.poll();
        }
        
        // 큐의 값을 차례대로 결과 배열에 저장하여 return
        for(int i = 0; i < k; i++) {
            answer[i] = pq.poll();
        }
        
        return answer;
    }
}

---