692. Top K Frequent Words

• IDE 의 도움을 받았지만 첫 시도에 accept 되었다. 성능은 좋지 않았다.
• 일단 words 를 iterate 하며 map 에 넣었고, 이후 pq 에 다시 넣었는데, 이때 pq 의 comparator 를 빈도수, 그다음 알파벳 순서로 지정하였다.
• 이후 pq 를 iterate 하며 string 을 list 에 넣어 return 하였다.
• PQ  선언할 때 PriorityQuene<>(n) 을 하면 아이템 개수를 n개 만큼만 허용하는 줄 알았는데, 그게 아니고 initial capacity 이다. 당연히 더 넣을수록 늘어난다. 
• 나의 복잡도는, word 개수를 N 이라고 하면, 
• 처음 hashmap put 할때 iterator O(N)
• pq 에 put  할때  O(NlogN)
• pq 에서 꺼내와서 list 에 넣을때 O(k)
• 해서 O(N)+O(NlogN)+O(k) 가 되는듯 하다.
• Trie  생각도 해봤는데, count 는 저장한다 쳐도, Top K 개를 어떻게 관리해서 꺼내올지를 몰라 접근하지 못했다.

• 답안을 보니, 나는 첫번째 답안과 두번째 답안을 합해서 풀었다. 첫번째처럼 풀꺼면 굳이 pq 를 도입하지 않고, map 의 keySet 만 가지고 Collections.sort 로 정렬 해버리면 된다. 
• pq  를 쓸꺼면, 한꺼번에 addAll 할것이 아니라, pq  에 넣을 때마다 pq 의 size 를 체크 해서 k 보다 크면 poll 을 해버렸어야 했다. 즉,

*내가 한 방법

pq.addAll(map.entrySet());
while(pq.iterator().hasNext()){
    list.add(pq.poll().getKey());
}

int cnt = 0;
List<String> list = new ArrayList<>();
while(pq.iterator().hasNext() && cnt <k){
    cnt++;
    list.add(pq.poll().getKey());
}
return list;

*collections 를 이용해 comparator 로 정렬 하고, sublist 를 return

List<String> candidates = new ArrayList(map.keySet());
Collections.sort(candidates, (w1, w2) -> map.get(w1).equals(map.get(w2)) ?
        w1.compareTo(w2) : map.get(w2) - map.get(w1));

return candidates.subList(0, k);

*pq 에 k개 만큼만 관리하면서 넣은 다음 poll 해서 reverse 한 결과를 return
for (String word: map.keySet()) {
    pq.offer(word);
    if (pq.size() > k) pq.poll();
}

List<String> ans = new ArrayList();
while (!pq.isEmpty()) ans.add(pq.poll());
Collections.reverse(ans);
return ans;