LeetCode - Top K Frequent Words

문제설명

1개이상의 문자열을 가진 배열이 주어진다.
가장 빈번한 문자열 k 개를 가진 리스트를 뽑아라

단 시간복잡도는 $O(n*log_2 n)$이어야 하며, 같은 복잡도가 있을경우 alphabetical 하게 만들어라.

해결방법

아무래도 주기를 나타내는 문제는 Hash를 사용하는게 적합하다고 생각이 들었다.
그래서 Hash를 사용했고, 다음 문제는 정렬이다.

위 문제에서 정렬의 우선순위는 2가지가 있다.
1순위는 빈번도가 가장 많아야할 것
2순위는 빈번도가 동일할 시 alphabetically 해야 할 것.

그래서 해쉬를 사용한 다음 해쉬를 위 조건에 맞춰 정렬해줘야 할 필요성을 느꼈다.
2가지의 방식을 떠올렸다
1. LinkedHashMap을 사용할 것
2. PriorityQueue를 사용할 것

둘다 시간복잡도가 $O(n*log_2 n)$ 을 가지기 때문에 어느것을 사용해도 문제가 없다 생각했고,
익숙한 PriorityQueue를 사용했다.

코드

import java.util.*;

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String,Integer> map = new HashMap<String,Integer>();
        PriorityQueue<Node> queue = new PriorityQueue<>();
        
        for(String word : words){
            if(!map.containsKey(word))
                map.put(word,0);
            int num = map.get(word);
            map.put(word,num+1);
        }
        
        for(String key : map.keySet())
            queue.add(new Node(key,map.get(key)));
        
        ArrayList<String> answer = new ArrayList<>();
        
        for(int i=0; i<k; i++){
            Node node= queue.poll();
            answer.add(node.word);
        }
        return answer;
    }
}

class Node implements Comparable<Node>{
    public String word;
    public int num;
    
    public Node(String word, int num){
        this.word=word;
        this.num=num;
    }
    
    @Override
    public int compareTo(Node other){
        if(num!=other.num)
            return -1*Integer.compare(num,other.num);
        else
            return word.compareTo(other.word);
    }
    
}

해결

생각한대로 해결되서 좋았다.

풀이시간 : 15분