힙(Heap) - 더 맵게 / 디스크 컨트롤러 / 이중우선순위큐

더 맵게

모든 음식이 K 이상이 될 때까지 섞어야 하는 최소 횟수를 구하는 문제

모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 두 개의 가장 낮은 스코빌 지수를 섞는 과정을 반복한다. 각 섞는 과정은 다음과 같다:

• 새로운 스코빌 지수 = (가장 낮은 스코빌 지수) + (두 번째로 낮은 스코빌 지수 * 2)

풀이 전략

1. 우선 순위 큐 사용
   • 가장 낮은 스코빌 지수를 효율적으로 추출하기 위해 최소 힙 사용
   • 최소 힙에서 가장 작은 두 원소를 추출해서 새로운 스코빌 지수를 계산
   • 새로 계산한 스코빌 지수를 다시 힙에 추가
2. 반복 조건
   • 힙의 최솟값이 K 이상이면 종료
   • 힙의 원소가 하나만 남았는데도 K 이상이 안되면, 더 이상 섞을 수 없으므로 -1 반환

알고리즘 풀이

// 최소 힙 클래스 정의
class MinHeap {
  constructor() {
    this.heap = []; // 힙 배열을 초기화
  }

  // 힙의 크기를 반환
  size() {
    return this.heap.length;
  }

  // 힙에서 두 인덱스의 값을 교환
  swap(idx1, idx2) {
    [this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]];
    return this.heap;
  }

  // 자식 노드의 부모 노드 인덱스를 반환
  getParentIdx(childIdx) {
    return Math.floor((childIdx - 1) / 2);
  }

  // 부모 노드의 왼쪽 자식 노드 인덱스를 반환
  getLeftChildIdx(parentIdx) {
    return parentIdx * 2 + 1;
  }

  // 부모 노드의 오른쪽 자식 노드 인덱스를 반환
  getRightChildIdx(parentIdx) {
    return parentIdx * 2 + 2;
  }

  // 힙에서 최솟값(루트)을 제거하고 반환
  heappop() {
    const heapSize = this.size();
    if (!heapSize) return null; // 힙이 비어있으면 null 반환
    if (heapSize === 1) return this.heap.pop(); // 힙에 하나만 남아있다면 제거 후 반환

    const value = this.heap[0]; // 루트 값 저장
    this.heap[0] = this.heap.pop(); // 마지막 값을 루트로 이동
    this.bubbledown(); // 힙 조건 유지
    return value; // 제거된 값 반환
  }

  // 힙에 새 값을 추가
  heappush(value) {
    this.heap.push(value); // 새 값을 힙 배열에 추가
    this.bubbleup(); // 힙 조건 유지
    return this.heap;
  }

  // 삽입된 값을 올려 힙 조건 유지
  bubbleup() {
    let child = this.size() - 1; // 마지막 요소의 인덱스
    let parent = this.getParentIdx(child); // 부모 노드의 인덱스

    // 부모보다 자식이 작은 동안 반복
    while (this.heap[child] < this.heap[parent]) {
      this.swap(child, parent); // 부모와 자식을 교환
      child = parent; // 부모를 새로운 자식으로 설정
      parent = this.getParentIdx(parent); // 새로운 부모 인덱스 계산
    }
  }

  // 루트 값을 내리며 힙 조건 유지
  bubbledown() {
    let parent = 0; // 루트 노드 인덱스
    let leftChild = this.getLeftChildIdx(parent); // 왼쪽 자식 인덱스
    let rightChild = this.getRightChildIdx(parent); // 오른쪽 자식 인덱스

    // 자식 중 하나라도 부모보다 작으면 반복
    while (
      (leftChild <= this.size() - 1 &&
        this.heap[leftChild] < this.heap[parent]) ||
      (rightChild <= this.size() - 1 &&
        this.heap[rightChild] < this.heap[parent])
    ) {
      // 오른쪽 자식이 더 작으면 오른쪽 자식과 교환
      if (
        rightChild <= this.size() - 1 &&
        this.heap[leftChild] > this.heap[rightChild]
      ) {
        this.swap(parent, rightChild);
        parent = rightChild; // 부모 인덱스를 오른쪽 자식으로 갱신
      } else {
        // 그렇지 않으면 왼쪽 자식과 교환
        this.swap(parent, leftChild);
        parent = leftChild; // 부모 인덱스를 왼쪽 자식으로 갱신
      }
      leftChild = this.getLeftChildIdx(parent); // 새로운 왼쪽 자식 인덱스 계산
      rightChild = this.getRightChildIdx(parent); // 새로운 오른쪽 자식 인덱스 계산
    }
  }
}

function solution(scoville, K) {
  let count = 0; // 섞은 횟수를 기록
  const heap = new MinHeap(); // 최소 힙 생성

  // 모든 스코빌 지수를 힙에 추가
  scoville.forEach((el) => heap.heappush(el));

  // 힙의 최솟값이 K 이상이 될 때까지 반복
  while (heap.heap[0] < K && heap.size() > 1) {
    count++; // 섞은 횟수 증가
    // 가장 맵지 않은 두 개의 음식을 섞어 새로운 스코빌 지수 계산
    heap.heappush(heap.heappop() + heap.heappop() * 2);
  }

  // 최종적으로 힙의 루트 값이 K 이상인지 확인
  return heap.heap[0] >= K ? count : -1; // 조건 만족 여부에 따라 결과 반환
}

시간 복잡도

• 힙 연산 시간:shift로 두 값을 추출한 후 새 값을 삽입해 정렬하므로, 한 번의 섞기 작업당 O(nlogn).
• 최대 연산 횟수:n번 작업을 반복할 수 있으므로, 총 시간 복잡도는 O(n2logn).

---

디스크 컨트롤러

모든 작업의 반환 시간(요청 시점부터 종료 시점까지 걸린 시간)의 평균의 정수 부분을 반환하는 문제

주어진 작업 jobs는 각각 작업의 요청 시점과 소요 시간으로 구성된다. 우선순위 디스크 컨트롤러는 소요 시간이 짧은 작업부터 처리하며, 요청 시점과 작업 종료 시점을 기준으로 반환 시간을 계산한다.

풀이 전략

1. 정렬
   • 작업들을 요청 시점을 기준으로 오름차순 정렬
2. 우선 순위 큐(소요 시간 기준 최소 힙) 사용
   • 작업의 소요 시간이 짧은 작업을 우선적으로 처리해야 하므로 최소 힙을 사용
     • 현재 시간 기준으로 요청된 작업을 최소 힙에 추가
     • 최소 힙에서 작업을 꺼내 처리하며 반환 시간 누적
     • 모든 작업을 처리할 때까지 반복
   • 요청된 작업은 모두 힙에 넣고 현재 작업이 끝난 시점에 따라 새로운 작업을 처리
3. 반환 시간의 평균 계산

알고리즘 풀이

function solution(jobs) {
  // 작업을 요청 시점 기준으로 정렬
  jobs.sort((a, b) => a[0] - b[0]);

  let currentTime = 0; // 현재 시간
  let totalTurnaroundTime = 0; // 총 반환 시간
  let jobCount = jobs.length; // 작업의 개수
  const minHeap = []; // 최소 힙 (작업 소요 시간 기준)

  let jobIndex = 0; // jobs 배열의 인덱스

  while (jobIndex < jobCount || minHeap.length > 0) {
    // 현재 시간까지 요청된 작업을 힙에 추가
    while (jobIndex < jobCount && jobs[jobIndex][0] <= currentTime) {
      const [requestTime, duration] = jobs[jobIndex];
      minHeap.push([duration, requestTime]); // 힙에는 [소요 시간, 요청 시점] 저장
      minHeap.sort((a, b) => a[0] - b[0]); // 힙 오름차순 정렬 (소요 시간 기준)
      jobIndex++;
    }

    // 힙이 비어 있으면 시간을 다음 요청 시점으로 이동
    if (minHeap.length === 0) {
      currentTime = jobs[jobIndex][0];
      continue;
    }

    // 가장 짧은 소요 시간을 가진 작업을 꺼내 처리
    const [duration, requestTime] = minHeap.shift();
    currentTime += duration; // 작업 소요 시간만큼 경과
    totalTurnaroundTime += currentTime - requestTime; // 반환 시간 누적
  }

  // 반환 시간 평균의 정수 부분 반환
  return Math.floor(totalTurnaroundTime / jobCount);
}

시간 복잡도

1. 정렬: 작업을 요청 시점 기준으로 정렬하므로 O(NlogN) (N은 작업의 개수)이다.
2. 힙 연산: 최소 힙에 작업을 추가하거나 제거하는 데 O(logN)이다.
3. 전체: 모든 작업을 처리하면서 정렬과 힙 연산을 수행하므로 최종 시간 복잡도는 O(NlogN)이다.

---

이중 우선순위 큐

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 반환하는 문제

풀이 전략

1. 최소 힙과 최대 힙 활용
   • 최소 힙은 값이 작은 순서대로 정렬.
   • 최대 힙은 값이 큰 순서대로 정렬.
2. 연산 처리
   • I 숫자: 최소 힙과 최대 힙에 값을 삽입.
   • D 1: 최대 힙에서 값을 삭제.
   • D -1: 최소 힙에서 값을 삭제.
   • 힙 간 동기화를 통해 중복된 값을 제거.

알고리즘 풀이

// 최소 힙 클래스 정의
class MinHeap {
  constructor() {
    // 최소 힙을 관리하는 배열, 첫 번째 자리는 사용하지 않음
    this.heap = [null];
  }

  // 값을 힙에 삽입하는 메서드
  push(val) {
    this.heap.push(val); // 값을 힙 배열에 추가
    let currentIndex = this.heap.length - 1; // 새로 추가된 값의 인덱스
    let parentIndex = Math.floor(currentIndex / 2); // 부모 노드의 인덱스 계산

    // 부모 노드가 존재하고, 현재 노드가 부모보다 작으면, 힙의 규칙에 맞게 위치를 변경
    while (
      parentIndex !== 0 &&
      this.heap[currentIndex] < this.heap[parentIndex]
    ) {
      this._swap(currentIndex, parentIndex); // 두 값을 교환
      currentIndex = parentIndex; // 현재 인덱스를 부모로 갱신
      parentIndex = Math.floor(currentIndex / 2); // 부모 노드의 인덱스 재계산
    }
  }

  // 최댓값 또는 최솟값을 삭제하는 메서드
  pop(isTopPop) {
    if (this.isEmpty()) return; // 힙이 비어 있으면 삭제 불가

    // 힙에 원소가 하나만 남은 경우
    if (this.heap.length === 2) return this.heap.pop(); // 마지막 값을 반환하고 힙에서 제거

    // 최솟값을 삭제할 경우: 부모 노드를 맨 마지막 값으로 대체하고 자식들과 비교하여 힙을 재구성
    if (!isTopPop) {
      const parentIndex = Math.floor((this.heap.length - 1) / 2); // 부모 노드 인덱스
      const lastLeaf = this.heap.slice(parentIndex); // 마지막 리프 노드들
      const max = Math.max(...lastLeaf); // 마지막 리프들 중 최댓값 찾기
      this._swap(parentIndex + lastLeaf.indexOf(max), this.heap.length - 1); // 최댓값을 맨 마지막 값과 교환
      return this.heap.pop(); // 마지막 값을 반환하고 힙에서 제거
    }

    // 최솟값을 삭제할 경우
    const val = this.heap[1]; // 힙의 루트(최솟값) 값 저장
    this.heap[1] = this.heap.pop(); // 루트를 삭제하고 마지막 값을 루트로 대체

    let currentIndex = 1; // 루트 인덱스
    let leftIndex = 2; // 왼쪽 자식 인덱스
    let rightIndex = 3; // 오른쪽 자식 인덱스

    // 자식 노드들이 존재하고, 현재 노드가 자식들보다 크면 힙을 재구성
    while (
      (this.heap[leftIndex] &&
        this.heap[currentIndex] > this.heap[leftIndex]) || // 왼쪽 자식이 존재하고, 크기가 더 크면
      (this.heap[rightIndex] && this.heap[currentIndex] > this.heap[rightIndex]) // 오른쪽 자식이 존재하고, 크기가 더 크면
    ) {
      // 왼쪽 자식이 없으면 오른쪽 자식과 교환
      if (this.heap[leftIndex] === undefined) {
        this._swap(rightIndex, currentIndex);
      }
      // 오른쪽 자식이 없으면 왼쪽 자식과 교환
      else if (this.heap[rightIndex] === undefined) {
        this._swap(leftIndex, currentIndex);
      }
      // 왼쪽 자식이 더 크면 오른쪽 자식과 교환
      else if (this.heap[leftIndex] > this.heap[rightIndex]) {
        this._swap(currentIndex, rightIndex);
        currentIndex = rightIndex; // 현재 인덱스를 오른쪽 자식으로 갱신
      }
      // 오른쪽 자식이 더 크면 왼쪽 자식과 교환
      else if (this.heap[leftIndex] <= this.heap[rightIndex]) {
        this._swap(currentIndex, leftIndex);
        currentIndex = leftIndex; // 현재 인덱스를 왼쪽 자식으로 갱신
      }

      // 자식 인덱스 재계산
      leftIndex = currentIndex * 2;
      rightIndex = currentIndex * 2 + 1;
    }

    return val; // 삭제된 값 반환
  }

  // 힙이 비어있는지 확인하는 메서드
  isEmpty() {
    return this.heap.length === 1; // 첫 번째 요소만 있는 경우 힙이 비어 있다고 판단
  }

  // 최댓값과 최솟값을 반환하는 메서드
  result() {
    // 힙이 비어 있을 때는 [0, 0]을 반환
    if (this.heap.length === 1) return [0, 0];

    // 힙에 값이 하나만 있을 때는 해당 값이 최댓값과 최솟값이므로 두 값을 동일하게 반환
    if (this.heap.length === 2) return [this.heap[1], this.heap[1]];

    // 최댓값을 마지막 리프 노드에서 찾고, 최솟값은 루트에서 찾음
    const parentIndex = Math.floor((this.heap.length - 1) / 2);
    const lastLeaf = this.heap.slice(parentIndex);
    const max = Math.max(...lastLeaf); // 최댓값 찾기
    return [max, this.heap[1]]; // 최댓값과 최솟값 반환
  }

  // 배열에서 두 인덱스의 값을 교환하는 메서드
  _swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]]; // 교환
  }
}

// solution 함수: 연산을 처리하여 결과를 반환
function solution(operations) {
  const minHeap = new MinHeap(); // 최소 힙 객체 생성

  // 연산을 하나씩 처리
  operations.forEach((operation) => {
    const [type, val] = operation
      .split(" ")
      .map((v, i) => (i === 1 ? Number(v) : v)); // 연산과 값을 분리
    if (type === "I") {
      // "I" 연산은 값을 삽입
      minHeap.push(val);
    } else {
      // "D" 연산은 값을 삭제, val < 0이면 최솟값 삭제, 그렇지 않으면 최댓값 삭제
      minHeap.pop(val < 0);
    }
  });

  // 연산이 끝난 후, 최댓값과 최솟값을 반환
  return minHeap.result();
}

시간 복잡도

• push: O(log N)
• pop: O(log N)
• 연산 처리와 힙 동기화는 각 연산마다 O(log N) 시간이 소요됩니다.