[프로그래머스][Javascript]더 맵게

문제

더 맵게

프로그래머스

 

코드

function solution(scoville, K) {
    var answer = 0;
    let s = scoville;
    
    
    for(let i =0;i<s.length;i++){
        s.sort((a,b)=>a-b);
        //console.log(s+"정렬");
        if(s[0]>=K){break;}
        
        s[0] = s[0] + 2*s[1];
        s[1] = Infinity;
        answer++;
        //console.log(s);
    }
    if(s[0] == Infinity){return -1;}
    else{return answer;}
}
//console.log(solution([1,1,1,1],100));

정확성 테스트 -> 통과

효율성 테스트 -> 시간 초과😓

 

📖효율성까지 통과한 다른 풀이

class Heap {
  constructor() {
    this.items = [];
  }

  swap(index1, index2) {
    [this.items[index1], this.items[index2]] = [
      this.items[index2],
      this.items[index1],
    ];
  }

  insert(val) {
    this.items.push(val);
    let index = this.items.length - 1;
    while (true) {
      let parentIndex = Math.floor((index - 1) / 2);
      //부모보다 자식이 작으면 자리 바꾸기
      if (this.items[index] < this.items[parentIndex]) {
        this.swap(index, parentIndex);
      } else break;
      index = parentIndex;
      if (index < 1) break;
    }
  }

  removeMin() {
    this.items[0] = this.items[this.items.length - 1];
    this.items.pop();
    if (this.items.length <= 1) return;

    let index = 0;
    while (true) {
      //두 자식중 작은값의 자식 인덱스 찾기
      let lChildIndex = index * 2 + 1;
      let rChildIndex = index * 2 + 2;
      let minIndex = index;
      if (
        lChildIndex < this.items.length &&
        this.items[minIndex] > this.items[lChildIndex]
      ) {
        minIndex = lChildIndex;
      }
      if (
        rChildIndex < this.items.length &&
        this.items[minIndex] > this.items[rChildIndex]
      ) {
        minIndex = rChildIndex;
      }
      //위치 바꾸기
      if (minIndex !== index) {
        this.swap(index, minIndex);
        index = minIndex;
      } else break;
    }
  }
}

function solution(scoville, K) {
  let answer = 0;

  //힙생성과 scoville 힙에 저장
  let scovilleHeap = new Heap();
  scoville.forEach((el) => {
    scovilleHeap.insert(el);
  });

  //스코빌 지수 설정
  while (true) {
    if (scovilleHeap.items[0] >= K) break;
    if (scovilleHeap.items.length <= 1) {
      answer = -1;
      break;
    }    

    const low1 = scovilleHeap.items[0];
    scovilleHeap.removeMin();
    const low2 = scovilleHeap.items[0];
    scovilleHeap.removeMin();
    scovilleHeap.insert(low1 + low2 * 2);

    answer++;
  }

  return answer;
}

 

✅checkpoint!

Infinity	무한대
힙이란?	-완전 이진트리 기반의 트리형 자료구조로써 최댓값이나 최솟값을 찾아내기 위해 사용 -최대 힙과 최소 힙이 존재
최대 힙	부모 노드의 키가 자식 노드의 키보다 같거나 큰 완전 이진 트리
최소 힙	자식 노드의 키가 부모 노드의 키보다 같거나 큰 완전 이진 트리

이 문제 참고 블로그