728x90
반응형
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 등 테크닉 쓰기
728x90
반응형
'공부 > 2024 항해99코딩클럽' 카테고리의 다른 글
99클럽 코테 스터디 36일차 TIL + [LeetCode] 2390. Removing Stars From a String/스택/큐/JAVA풀이 (0) | 2024.06.24 |
---|---|
99클럽 코테 스터디 34일차 TIL + [LeetCode] 1823. Find the Winner of the Circular Game/스택/큐/JAVA풀이/원형리스트 (0) | 2024.06.22 |
99클럽 코테 스터디 31일차 TIL + 좋은 코드를 작성하기위한 방법 (0) | 2024.06.19 |
99클럽 코테 스터디 30일차 TIL + 해시맵 (1) | 2024.06.19 |
99클럽 코테 스터디 29일차 TIL + ArrayList (0) | 2024.06.17 |