[LeetCode] 692, 347 Top K Frequent Words, Top K Frequent Elements JavaScript

문제 링크

Top K Frequent Words - LeetCode

Top K Frequent Elements - LeetCode

 

문제 유형

해쉬 맵, 정렬

 

문제 풀이

두 문제는 각각 주어진 문자열 배열과 숫자 배열에서 가장 많이 나온 k개의 원소들을 출력하는 문제이다.

추가적으로 첫 번째 문제는 가장 많이 나온 단어 순으로 정렬하되, 나온 횟수가 똑같은 단어는 사전순으로 정렬을 해줘야 한다.

따라서, 각 원소를 키로 갖고 나온 횟수를 값으로 갖는 해쉬 맵을 만들고 키의 원소들을 값을 비교하며 정렬을 해주면 된다.

배열의 크기가 n일 때, 해쉬 맵을 만드는데 O(n)의 시간 복잡도를 갖는다. 그리고 정렬을 하는데 O(nlogn)의 시간  복잡도가 가지므로 최종적으로 O(nlogn)의 시간복잡도를 갖게 된다.

 

추가) 해쉬 맵을 생성한 뒤 가장 많이 나온 k개의 원소를 찾을 때 힙(Heap)을 이용하면 O(nlogk)의 시간복잡도로 문제를 해결할 수 있다.

힙(Heap)을 공부한 후 힙으로 다시 문제를 풀어봐야지,,😁

 

코드

// 692. Top K Frequent Words
var topKFrequent = function(words, k) {
    const map = new Map();
    
    for (let i = 0; i < words.length; i++) {
        map.set(words[i], map.get(words[i]) + 1 || 1);
    }
    
    const answer = [...map.keys()].sort((a, b) => {
    	// 나온 횟수가 같을 경우(0)에는 사전순으로 정렬
        return map.get(b) - map.get(a) || a.localeCompare(b);
    });
    return answer.slice(0, k);
};

// 347. Top K Frequent Elements
var topKFrequent = function(nums, k) {
    const map = new Map();
    
    nums.forEach((e) => map.set(e, map.get(e) + 1 || 1));
    return [...map.keys()].sort((a, b) => map.get(b) - map.get(a)).slice(0, k);
};

 

참고

https://www.youtube.com/watch?v=6CD5EzjCZPA