692. Top K Frequent Words

💡 풀이

// O(NlogN)
var topKFrequent = function (words, k) {
  let obj = {};

  for (let i = 0; i < words.length; i++) {
    if (!obj[words[i]]) obj[words[i]] = 1;
    else obj[words[i]]++;
  }

  let keys = Object.keys(obj);

  let sorted = keys.sort((a, b) => {
    let compareFunc = obj[b] - obj[a];
    return compareFunc === 0 ? a.localeCompare(b) : compareFunc;
  });

  let answer = sorted.slice(0, k);

  return answer;
};

📝 결과

📝 정리

역시나 HashMap 관련 문제다. keys 배열을 정렬할 때 NlogN의 시간이 걸렸다. 문제의 요구사항은 - words 배열의 단어가 나온 횟수에 따라 정렬하되, output 배열의 length는 k여야 한다. 또한, 나온 횟수가 같다면 사전 순서대로 정렬해야 한다 - 라는 것이다. 이를 코드로 표현하면 다음과 같다.

• obj 객체에 단어가 나온 횟수를 value 값, 단어 자체를 key값으로 만들어 반복문을 돌린다.

• obj 객체의 key들을 value값에 따라 정렬하되, 같은 value가 있는 경우 사전순으로 정렬한다. (sorted를 정렬한 코드를 확인하면 됨)

• output 배열의 요소는 k개기 때문에, 정렬된 배열을 slice(0,k)를 이용해서 잘라준다.

이 문제는 O(Nlogk)의 시간 복잡도로 해결할 수 있다고도 한다. Heap을 사용하면 되는데, 아직 방법을 생각해내지 못해서 다음에 Heap 관련 문제를 더 풀 때 이 문제를 다시 봐야겠다!

수정, 지적을 환영합니다!

문제 링크

https://leetcode.com/problems/top-k-frequent-words/

LeetCode GitHub

https://github.com/tTab1204/LeetCode