[Refresh ! 코딩 테스트 / js] -더 맵게

문제 해석

• 전형적인 heap 문제
• 하지만 js는 heap 이 없어서 빡구현 해야됨
• heap 구조는 https://chamdom.blog/heap-using-js/ 여기서 설명이 잘되어있다.

Minheap , Maxheap 두가지

• minheap 은 당연히 index =0 인 맨 꼭데기가 가장 작아야되며
• maxheap 은 당연히 index=0 인 맨 꼭데기가 가장 커야됨

Question !

그러면 왜 맨끝에서 pop 해서 처음부터 다시 정렬을?

• 이문제에 대해서 생각을 해봤는데 . 결국은 우리가 비교해야될것은 같은 자식이고 . 서로 경쟁을 해서 알고보니 내가 형이더라 ㅋ 이런 식으로 정렬을 해야된다.
• 따라서 정렬의 기준을 가장 관련없는듯한 맨 끝의 수로 정렬을 하면된다.

나의 코드

    class Heap{
          constructor() {
            this.heap = [];
        }
        getParentIndex(index){
            return Math.floor((index-1) /2);
        }
        //최소힙을 구현하시오 
        //1, swap 함수 2. 두번빼고 3. 하나넣고 다시 순서 
         swap(index1,index2){
            [this.heap[index1],this.heap[index2]]= [this.heap[index2],this.heap[index1]]
        }
        insert(element){
            this.heap.push(element)
            this.getparent()
        }
         getparent(){
         let  start= this.heap.length-1;
           // 맨 끝에 있는거 
         let parent= this.getParentIndex(start);
            // 부모 인덱스가 0 이상일때 while 문으로 부모와 자식의 위치를 바꿔보자
           while(parent>=0){
               if(this.heap[start]<this.heap[parent]){
                   //작은거를 위로 올려야된다고 가정. 부모와 자식간의 관계를바꾸자 
                    this.swap(start,parent);
                    start=parent;
                    parent= this.getParentIndex(start);
               }
               else{
                   break;
               }
               
           }
           
           
       }
      downpop(){
          //잴 위에 있는거를 하나 빼고 , 나머지를 정렬하는 함수 
          // 이거는 마지막에 return 값으로 뺄거임
           let top= this.heap[0];
           let final_heap= this.heap[this.heap.length-1];
           this.heap[0]= final_heap;
           this.heap.pop();
          // 이제 순서 바꾸는거 시작하는거 
          this.Getdown();
          // 하나 뽑고 함수 실행 이라고 생각
          return top; 
          
      }
      Getdown(){
          let start=0;
          
          while(start<this.heap.length-1){
              let right_edege= start*2+1;
              let letf_edge= start*2+2;
              //오른쪽 노드와 왼쪽 노드를 선언함
               //이제 누가 더 큰지에 따라서 움직이는 곳이 다를듯
              //우리가 찾아야될거에 집중 .. > 작은걸 찾아야됨으로 더 작은게 오른족에 있는지 왼쪽에 있는지를 찾는 if 문
              if( right_edege<this.heap.length && this.heap[right_edege]>this.heap[letf_edge]){
                  right_edege=letf_edge;
              }
              //작은거 찾았으니 이제 이동
              if(this.heap[start]> this.heap[right_edege]){
                  //인경우에 
                  this.swap(start, right_edege);
                  start=right_edege;
              }
              else{
                  break;
              }
              
          }
          
      }
     peek(){
         return this.heap[0];
     }
        size(){
            return this.heap.length;
            
        }
        
        
        
    }


function solution(scoville, K) {

    const start_heap= new Heap();
    for( const hey of scoville ){
         start_heap.insert(hey);

    }
    let count=0;
    while( start_heap.size()>=2 &&start_heap.peek()<K ){
       const first= start_heap.downpop();
       const second= start_heap.downpop();
        start_heap.insert(first+(second*2));
        count+=1;
    }
    
    return start_heap.peek() >=K ?count :-1 
 
    
}