Top K Frequent Elements

내 풀이

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number[]}
     */
    topKFrequent(nums, k) {
        let answer=[];
        let count={};
        for (let i=0;i<nums.length;i++){
            if (!count[nums[i]]){
                count[nums[i]]=1;
            }else{
                count[nums[i]]+=1;
            }
        }
        let pairs = Object.entries(count);
        pairs=pairs.sort((a,b)=>b[1]-a[1]);
        while(answer.length<k){
            let [num, numCount]=pairs.shift();
            answer.push(num)
        }
        return answer;
        
    }
}

시간복잡도: O(nlogn)
흐름설명
1. 객체를 만들어서 그 안에 숫자:그 숫자 갯수 넣음
2. Object, entries로 [숫자, 그 숫자 갯수]로 이루어진 배열 만듦.
3. 이 배열을 그 숫자 갯수 내림차순으로 sort함.
4. while문 내에서 answer 길이가 k가 될 때까지 배열에서 앞에거 빼서 집어넣음.

다른 풀이1: Sorting

사실상 나랑 똑같은 코드인데 훨씬 깔끔하다.
그리고 아래 코드 보면서 알게 된건데, 만약 TypeScript였으면 내 코드는 틀렸을 것이다. 자바스크립트는 느슨한 언어라서 parseInt를 안 해줘도 괜찮은데 만약 타입에 엄격한 언어였으면 틀렸다.

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number[]}
     */
    topKFrequent(nums, k) {
      const count={};
      for (const num of nums){
      	count[num]=(count[num] || 0)+1 // 이거 진짜 굉장하다.
      }
      cosnt arr=Object.entries(count).map(([num, freq])=>[freq, parseInt(num)]);
      arr.sort((a,b)=>b[0]-a[0]);
      return arr.slice(0,k).map(pair=>pair[1]);
    }
}

다른 풀이2: Min-Heap

프로그래머스는 자바스크립트 우선순위큐를 왜 지원을 안할까^^ 자바스크립트로 코테 하는 사람들에게 아주 불리한 자료구조...^^ 하... MinPriorityQueue 좀 지원해주세요 리트코드는 지원해주는데 왜 백준이랑 프로그래머스는 안해주시는건데요... (미국과 한국에서의 자바스크립트의 위상이 다르기 때문입니다.)

class MinHeap{
  constructor(){
    this.heap=[];
  }
  size(){
    return this.heap.length;
  }
  peek(){
    return this.heap[0];
  }
  swap(i,j){
    [this.heap[i], this.heap[j]]=[this.heap[j], this.heap[i]];
  }
  enqueue(value){
    this.heap.push(value);
    this.bubbleUp();
  }
  bubbleUp(){
    let index=this.heap.length-1;
    while(index>0){
      let parentIndex=Math.floor((index-1)/2);
      if (this.heap[parentIndex][1]<=this.heap[index][1]){
        break;
      }
      this.swap(parentIndex, index);
      index=parentIndex;
    }
  }
  dequeue(){
    if (this.heap.length===1){
      return this.heap.pop();
    }
    const min this.heap[0];
    this.heap[0]=this.heap.pop();
    this.bubbleDown();
    return min;
  }
  bubbleDown(){
    let index=0;
    const length=this.heap.length;
    while(true){
      let left=index*2 +1;
      let right=index * 2 +2;
      let smallest=index;
      
      if (left < length && this.heap[left][1] < this.heap[smallest][1]) {
        smallest = left;
      }
      if (right < length && this.heap[right][1] < this.heap[smallest][1]) {
        smallest = right;
      }
      if (smallest === index) break;
      
      this.swap(index, smallest);
      index = smallest;
    }
  }
  
}


class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number[]}
     */
    topKFrequent(nums, k) {
      const count={};
      for (const num of nums){
        count[num]=(count[num]||0)+1;
      }
      const heap = new MinHeap();
    
      for (const [num, freq] of Object.entries(count)) {
        heap.enqueue([num, freq]);
        if (heap.size() > k) {
          heap.dequeue();
        }
      }
    
      const res = [];
      while (heap.size() > 0) {
        res.push(heap.dequeue()[0]);
      }

      return res.reverse();
  }
}