Level 2 ) 더 맵게 ⭐️

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

scoville의 길이는 2 이상 1,000,000 이하입니다.
K는 0 이상 1,000,000,000 이하입니다.
scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

입출력 예

scoville	K	return
[1, 2, 3, 9, 10, 12]	7	2

입출력 예 설명

스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

풀이

1. 스코빌 배열을 오른차순으로 정렬해준다.
2. arr에 스코빌의 가장 작은 두 값을 넣는다.
3. arr의 가장 작은 값이 K보다 같거나 크면 answer를 반환한다.
4. arr의 가장 작은 값이 K보다 작으면,
   • 섞은 값을 만들고 스코빌에서 다음 값을 가져와 arr에 다시 세팅한다.
     이때 섞은 값과 다음 값을 오름차순으로 넣어준다.
     answer를 증가시켜준다.
   • i가 가장 마지막까지 오면 mix된 값이 K보다 같거나 클 때 answer + 1, 아니면 -1을 반환한다.

-> 무조건 순서대로만 하려다가 아래 경우를 고려하지 못했다.

scoville = [1, 1, 1, 1, 1], K = 2, return = 3

이렇게 되어야 하는데,
1. 3 1 1 1
2. 3 3 1
3. 3 7

내가 만든 풀이는 아래처럼 된다.
1. 1 3 1 1
2. 7 1 1
3. 15 1
4. 31

function solution(scoville, K) {
    let answer = 0;
    scoville.sort((a,b) => a-b);
    let arr = scoville.slice(0,2);
    for(let i=2;i<scoville.length + 1;i++){
        if(arr[0] >= K) return answer;
        let mixed = arr[0] + (arr[1] * 2);
        if(i === scoville.length){
            return mixed >= K ? answer + 1 : -1;
        }else{
            let next = scoville[i];
            arr = [Math.min(mixed,next), Math.max(mixed,next)];
            answer++;
        }
    }
}

다른 풀이

1. 섞은 값을 넣고 사용한 값은 pop으로 제거.
2. 정렬해가면서 항상 가장 작은 두 값으로 섞은 값 만들 수 있도록.

-> 시간 초과

function solution(scoville, K) {
    let answer = 0;
    scoville.sort((a,b) => b-a);
    while(scoville.at(-1) < K){
        if(scoville.length === 1) return -1;
        scoville.unshift(scoville.at(-1) + (scoville.at(-2) * 2));
        scoville.pop();
        scoville.pop();
        answer++;
        scoville.sort((a,b) => b-a);
    }
    return answer;
}

최소 힙을 이용한 풀이

class MinHeap {
  constructor() {
    this.heap = [];
  }

  size() {
    return this.heap.length;
  }
      
    // 값을 넣되, 오름차순 정렬함
  push(value) {
    this.heap.push(value);
    let currentIndex = this.heap.length - 1;

    while (
      currentIndex > 0 &&
      this.heap[currentIndex] < this.heap[Math.floor((currentIndex - 1) / 2)]
    ) {
      const temp = this.heap[currentIndex];
      this.heap[currentIndex] = this.heap[Math.floor((currentIndex - 1) / 2)];
      this.heap[Math.floor((currentIndex - 1) / 2)] = temp;
      currentIndex = Math.floor((currentIndex - 1) / 2);
    }
  }

    // 값을 빼되, 오름차순 정렬 함
  pop() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();

    const minValue = this.heap[0];
    this.heap[0] = this.heap.pop();
    let currentIndex = 0;

    while (currentIndex * 2 + 1 < this.heap.length) {
      let minChildIndex = currentIndex * 2 + 2 < this.heap.length && this.heap[currentIndex * 2 + 2] < this.heap[currentIndex * 2 + 1] ? currentIndex * 2 + 2 : currentIndex * 2 + 1;

      if (this.heap[currentIndex] < this.heap[minChildIndex]) {
        break;
      }

      const temp = this.heap[currentIndex];
      this.heap[currentIndex] = this.heap[minChildIndex];
      this.heap[minChildIndex] = temp;
      currentIndex = minChildIndex;
    }

    return minValue;
  }

  peek() {
    return this.heap[0];
  }
}

function solution(scoville, K) {
  const minHeap = new MinHeap();

  for (const sco of scoville) {
    minHeap.push(sco);
  }

  let mixedCount = 0;

  while (minHeap.size() >= 2 && minHeap.peek() < K) {
    const first = minHeap.pop();
    const second = minHeap.pop();
    const mixedScov = first + second * 2;
    minHeap.push(mixedScov);
    mixedCount++;
  }

  return minHeap.peek() >= K ? mixedCount : -1;
}

https://velog.io/@kwb020312/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%8D%94-%EB%A7%B5%EA%B2%8C

우선순위 큐를 이용한 풀이

class PriorityQueue {
  constructor() {
    this.heap = [];
  }

  size() {
      return this.heap.length;
  }

  empty() {
    return this.heap.length === 0;
  }

  peek() {
    return this.heap[0];
  }

  push(data) {
    this.heap.push(data);

    let i = this.heap.length - 1;
    while (i > 0) {
      const parent = ~~((i - 1) / 2);
      if (this.heap[parent] <= this.heap[i]) break;
      [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
      i = parent;
    }
  }

  pop() {
    if (this.empty()) return;

    const value = this.peek();
    [this.heap[0], this.heap[this.heap.length - 1]] = [
      this.heap[this.heap.length - 1],
      this.heap[0],
    ];
    this.heap.pop();
    this._heapify();
    return value;
  }

  _heapify() {
    const x = this.peek();
    const n = this.heap.length;
    let cur = 0;

    while (2 * cur + 1 < n) {
      const leftChild = 2 * cur + 1;
      const rightChild = leftChild + 1;
      const smallerChild =
        rightChild < n && this.heap[rightChild] < this.heap[leftChild]
          ? rightChild
          : leftChild;

      if (x > this.heap[smallerChild]) {
        [this.heap[cur], this.heap[smallerChild]] = [
          this.heap[smallerChild],
          this.heap[cur],
        ];
        cur = smallerChild;
      } else {
        break;
      }
    }
  }
}

function solution(scoville, K) {
    const n = scoville.length;
    let count = -1;

    const pq = new PriorityQueue();
    scoville.forEach(scov => pq.push(scov));

    while(pq.size() > 1){
        if(pq.peek() >= K) break;

        const first = pq.pop();
        const second = pq.pop();   
        const newFood = first + second * 2;
        pq.push(newFood);
    }

    const underK = Object.values(pq)[0].find(value => value < K);
    if(!underK) count = n - pq.size();
    return count;
}