문제

Top K Frequent Elements - LeetCode

Code

1차 풀이

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] answer = new int[k];
        Map<Integer, Integer> numsMap = new HashMap<>();
        
				// 각 숫자별 빈도수 세기
        for (int num: nums){
            numsMap.put(num, numsMap.getOrDefault(num, 0) + 1);
        }
	
				// 빈도수(value)기준으로 내림차순 정렬하기
        List<Map.Entry<Integer, Integer>> entries = numsMap.entrySet().stream()
                .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
                .collect(Collectors.toList());
				
				// 가장 많이 나온 k개 뽑기
        for (int i = 0; i < k; i++){
            answer[i] = entries.get(i).getKey();
        }

        return answer;
    }
}

• {숫자: 빈도수}의 형태로 Map에 저장한 뒤 stream의 sort를 이용하여 빈도수를 기준으로 내림차순으로 정렬하여 list로 뽑아내었다.
  

다른 풀이

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] answer = new int[k];
        Map<Integer, Integer> freqMap = new HashMap<>();
        PriorityQueue<int[]> pq = new PriorityQueue<>(((o1, o2) -> o2[1] - o1[1]));

				// 숫자 별 빈도수 Mapping하기
        for (int num: nums){
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }
			
				// 우선순위 큐에 넣기
        for (int num: freqMap.keySet()){
            pq.add(new int[]{num, freqMap.get(num)});
        }
				
				// k개 만큼 뽑기
        for (int i = 0; i < k; i ++){
            answer[i] = pq.poll()[0];
        }

        return answer;
    }
}

• 우선순위 큐를 이용한 풀이이다.
• 일반 정렬하는 것 보다 빠름을 알 수 있다.