99클럽 코테 스터디 32일차 TIL + [LeetCode] 347. Top K Frequent Elements 정렬

 

 

 

 

 

 

1. 오늘의 학습 키워드

---

 

 

[LeetCode] 347. Top K Frequent Elements 정렬

 

2. 오늘의 학습 문제 

---

문제

---

 

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

 

 

코드

---

import java.util.*;


class Solution {



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

        HashMap <Integer, Integer> frequentMap = new HashMap<Integer, Integer>() ;   // num을 키로하고 개수를 담는 해시맵 초기화 

        for(int num: nums){
            int keyValue= 0 ;
            if(frequentMap.containsKey(num)){ //해시맵의 키에 num이 있으면  
                keyValue=frequentMap.get(num) ; //현재 num에 해당하는 value값 가져옴 
            }

            frequentMap.put(num, keyValue +1);
        }

        
        Map<Integer, List<Integer>> freMultiMap = new HashMap <Integer, List<Integer>> (); //빈도: 키리스트를 담는 멀티해시맵

        for (Map.Entry<Integer, Integer> entry : frequentMap.entrySet()) {
            int freq= frequentMap.get(entry.getKey()); //현재 num에 대한 빈도 
            if(!freMultiMap.containsKey( freq)){
                freMultiMap.put(freq, new ArrayList<Integer>());
            }
            freMultiMap.get(freq).add(entry.getKey()); // 현재 키값을 빈도에 대해 추가 
        };

    
        List<Integer> allValues = new ArrayList<>();

        for (Map.Entry<Integer, List<Integer>> entry : freMultiMap.entrySet()) { //해시맵에 대해 키값들을 모두 arrayList에 담아줌
            allValues.addAll(entry.getValue());
        }


        int[] answer=new int[k];

        int size = allValues.size();
        for (int i = 0; i < k; i++) { //끝에서부터 k개의 원소만 answer에 담음
            answer[i] = allValues.get(size - k + i);
        }
        return answer;
    }
}

 

 

1. 먼저 해시맵을 선언하여 num:빈도를 담아준다. 

2. 선언한 해시맵에 대하여 역으로 빈도:num List를 담는 멀티해시맵을 새로 만든다. 

3. 멀티해시맵에 대하여 값들을 모두 arrayList에 담아주고, 끝에서부터 k번째 원소만 answer배열에 담는다. 

 

복잡도는 O(n)이다. 

 

3. 오늘의 회고

---

 

• entrySet 메서드를 사용했을 때, 키의 삽입 순서에 상관없이 Integer형태의 key가 오름차순으로 정렬되어 접근되었다. 해시맵은 키에 대한 순서가 없는데 왜일까 찾아보고, 세션에서 질문도 드려보았다. 
• 해시맵은 순서가 없다. 하지만 해시맵의 내부 알고리즘에 해시값이 이용되는데, 그 경향성이 있을 것 같다는 답변을 받았다. 
• 해시값에 주목해서 이 부분을 좀 더 서치해보려고 한다! 
• getOrDefault & merge 메서드를 써보자  + PriorityQueue
• CountingSort로 간단하게 풀 수 있다. 하지만 음수가 나올 수 있으니 BASE 등 테크닉 쓰기 

 

 

https://woocho.tistory.com/16

[JAVA] Map에서 key의 순서가 있을까?