[알고리즘] Leetcode_347_Tok_K_Frequent_Elements

Problem

Solve

 public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        //int[] 배열을 값으로 하는 우선순위 큐 -> 배열의 두번째 요소를 기준으로 내림차순 정렬된 큐
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->b[1]-a[1]);
		
        //배열을 순회하며 map에 num, count 저장
        for(int num : nums){
            map.put(num, map.getOrDefault(num,0)+1);
        }

		//map의 key 값에 따라 pq에 추가
        for(int key : map.keySet()){
            pq.add(new int[]{key, map.get(key)});
        }
        
        //pq에는 횟수를 기준으로 내림차순 정렬된 int[] 
        int[] answer = new int[k];
        for(int i = 0 ; i < k ; i++){
            answer[i] = pq.poll()[0];
            //반환배열에는 값이기 때문에 pq의 첫번째 요소를 할당
        }
        return answer;
    }

우선순위 큐 Priority Queue

일반적인 큐를 확장한 것으로 키와 값의 체계를 사용한다.
큐의 구조인 FIFO(First In First Out)을 가지며, 우선순위를 정해 높은 우선순위를 가진 데이터가 먼저 나가는 자료구조이다.
우선순위 큐에 저장할 객체는 필수적으로 Comparable Interface 를 구현해야 우선순위를 정할 수 있다. compareTo 를 override 하여 조건을 리턴해주면 높은 객체를 추출해준다.
내부 요소는 Heap으로 구성되어 이진트리 구조로 이루어져 있고 시간 복잡도는 O(NlogN)이다.

 //최소힙 (deafult) => 낮은 수가 우선순위
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
//최대힙 => 높은 수가 우선순위
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); 


//값 추가 
minHeap.add(1);
minHeap.offer(2);

//값 삭제
minHeap.poll(); 
minHeap.remove();

//초기화
minHeap.clear();