feat: [Lv. 2] 더 맵게 (JS/TS)

https://school.programmers.co.kr/learn/courses/30/lessons/42626

1. 문제분석
섞인 스코빌 = min1 스코빌 + min2 스코빌*2 -> 스코빌 >= K 까지 반복
-> N은 2~100만, 원소는 0~100만, K는 0~10억 -> 최소회수 리턴 (불가능시 -1)
섞은 결과가 아님 -> 모든 항목이 전부 K 이상이어야 함
-> min1이 K 이상이어야 함 -> 섞었을 때 min1이 아닐 수 있음
입력이 정렬되어 있지 않을 수도 있음!

2. 풀어보기
[1,2,3,9,10,12], 목표 7 -> 1+2*2=5 -> [3,5,9,10,12] -> 3+5*2=13 -> [9,10,12,13] -> 2 리턴

3. 슈도코드
scoville [] -> 정렬 -> 탑이 k보다 작으면 -> 2개 뽑아서 계산하고 넣음 -> 재정렬 -> 반복
-> 정렬로 간다면 -> O(NlogN) + O(N*NlogN) -> N=100만 * logN≈20 = 2조 -> 정렬은 NlogN
scoville [] -> 히피파이 -> 탑이 k보다 작으면 -> 2개 뽑아서 계산하고 넣음 -> 반복
-> 힙으로 간다면 -> O(N) + O(N*(3logN)) -> N=100만 * logN≈20 = 2000만

 

4. 구현코드

const solution = (scoville: number[], K: number) => {
  if (scoville.length === 0) {
    return -1;
  }
  if (scoville.length === 1) {
    return scoville[0] >= K ? 0 : -1;
  }
  if (scoville.every((s) => s >= K)) {
    return 0;
  }

  return byHeap(scoville, K);
};

const byHeap = (scoville: number[], K: number) => {
  const heap = new Heap<number>('MIN', scoville);

  while (heap.size() >= 2 && heap.peek() < K) {
    heap.push(heap.pop()! + heap.pop()! * 2); // 2개 보장됨
  }

  return heap.peek() >= K ? scoville.length - heap.size() : -1;
};

class Heap<T>; // 힙 구현은 https://ha2el.tistory.com/23 참고

 

5. 풀이회고

힙을 활용해서 최소값을 솎아내는 간단한 문제였다. 다만 JS/TS에는 힙 구현체가 없기 때문에, 직접 구현하느라 꽤 시간을 소모했다.

겸사겸사 최소힙/최대힙 전환해서 쓸 수 있게 구현해뒀고, 필요하면 우선순위큐로도 사용할 수 있도록 했다.

다음번에 최소힙/최대힙이나 우선순위큐가 필요한 문제를 만났을 때, 해당 코드 활용해서 시간을 단축하면 좋을 것 같다.