Leetcode 347. Top K Frequent Elements

오늘은 릿코드 347번 문제(Top K Frequent Elements)를 풀어보도록 하겠습니다.

 

Medium

 

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

 

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

 

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

 

이 문제는 freqs라는 오브젝트를 이용해 풀어보겠습니다.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    const freqs = {};
    for (let num of nums) {
        if (freqs[num] === undefined) { 
            freqs[num] = 1; 
        } else {
            freqs[num] = freqs[num] + 1;
        }
    }
    
    const frequencyArray = [];
    for (key in freqs) {
        frequencyArray.push([freqs[key], key]);
    }
    
    frequencyArray.sort((a, b) => {
        return b[0] - a[0];
    });
    
    const mostFreq = [];
    for (let i = 0; i < k; i++) {
        mostFreq.push(frequencyArray[i][1]);
    }
    
    return mostFreq;
};

생성된 오브젝트에 우선 키 값으로는 각 배열의 인자, 밸류로는 해당 키 숫자가 나온 빈도수를 넣습니다.

var nums = [1,1,1,2,2,3];

예제 1의 경우에는 아래와 같이 freqs 오브젝트가 생성이 되겠습니다.

Key	Value
'1'	3
'2'	2
'3'	1

1의 값이 3번 등장, 2의 값이 2번 등장, 3의 값이 1번 등장합니다.

처음 for loop 가 끝나게 되면 위의 표와 같이 freqs 오브젝트가 만들어 집니다.

생성된 키 밸류 값을 배열로 만들어 아래와 같이 키는 밸류로, 밸류는 키로 지정을 해 줍니다.

그리고 키 값을 기준으로 정렬을 해 줍니다.

var nums = [1,1,1,2,2,3,3,3,3,4,4,5,5,5,5];
var k = 3;

예제 1번의 경우 상관없지만 위와 같은 경우, 정렬 전과 정렬 후가 아래와 같이 달라지게 됩니다.

이렇게 정렬을 끝 마쳤으면 k 번째까지 루프를 돌면서 밸류값들로 mostFreq 배열에 append 하며 한 결과를 리턴해 주면 되겠죠?

---

오브젝트 이용 풀이 성능

잘 통과된 것을 확인 할 수 있습니다.

오늘은 릿코드 347번 문제 Top K Frequent Elements를 풀어보았습니다.

질문 사항 있으시면 댓글 남겨주세요!

※ 앞으로 모든 문제를 JavaScript 로 올릴 예정입니다.

다른 문제 풀이도 깃헙에서 확인 할 수 있습니다.