최소 힙(Min Heap)과 최대 힙(Max Heap) 2

우선순위 큐 문제와 힙 문제는 응용력 또한 중요한 것 같다.

 

문제

https://www.acmicpc.net/problem/13904

 

풀이

접근 방식

1. 모든 과제를 점수 기준으로 내림차순 정렬한다.
2. 가장 늦은 날부터 1일까지 거꾸로 순회하면서, 해당 날짜에 할 수 있는 과제 중 점수가 가장 높은 것을 선택한다.
   • 이를 위해 해당 날짜에 가능한 과제를 저장할 배열이나 자료구조가 필요하다.
3. 일정을 관리하는 방식은 배열을 사용해도 충분하다.

코드

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

  push(v) {
    this.heap.push(v);
    this.bubbleUp();
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    let last = this.heap[index];

    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);

      if (last >= this.heap[parentIndex]) break;
      this.heap[index] = this.heap[parentIndex];
      index = parentIndex;
    }

    this.heap[index] = last;
  }

  pop() {
    if (this.heap.length === 0) return 0;
    if (this.heap.length === 1) return this.heap.pop();

    let top = this.heap[0];
    let last = this.heap.pop();
    this.heap[0] = last;
    this.bubbleDown();
    return top;
  }

  bubbleDown() {
    let index = 0;
    const length = this.heap.length;

    while (true) {
      let left = index * 2 + 1;
      let right = index * 2 + 2;
      let smallest = index;

      if (left < length && this.heap[left] < this.heap[smallest]) {
        smallest = left;
      }

      if (right < length && this.heap[right] < this.heap[smallest]) {
        smallest = right;
      }

      if (index === smallest) break;
      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      index = smallest;
    }
  }

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

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

// 입력 처리
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const n = +input[0];
const dw = input.slice(1).map((v) => v.split(' ').map(Number));

// 마감일 기준으로 정렬
dw.sort((a, b) => a[0] - b[0]);

const heap = new MinHeap();

for (let [d, w] of dw) {
  if (heap.size() < d) {
    heap.push(w);
  } else if (heap.top() < w) {
    heap.pop();
    heap.push(w);
  }
}

// 결과 출력
console.log(heap.heap.reduce((a, c) => a + c, 0));

 

• 마감일 기준으로 정렬한 후, 현재 과제를 처리할 수 있는 날이 남아 있다면 수행.
• 그렇지 않다면 현재 heap에서 가장 점수가 낮은 과제와 비교하여, 점수가 더 크다면 교체.
• MinHeap을 통해 현재까지 수행한 과제 중 가장 점수가 낮은 것을 빠르게 꺼내어 교체 가능.

예시 따라가기

 

시작: heap = []

1. [1, 20]

• heap size(0) < d(1) → push
• heap = [20]

2. [2, 50]

• heap size(1) < d(2) → push
• heap = [20, 50]

3. [3, 30]

• heap size(2) < d(3) → push
• heap = [20, 50, 30]
  (자동정렬 → MinHeap이라 가장 작은 값이 top)

4. [4, 60]

• heap size(3) < d(4) → push
• heap = [20, 50, 30, 60]

5. [4, 40]

• heap size(4) == d(4)
• heap.top() = 20 < 40 → pop 20, push 40
• heap = [30, 50, 60, 40] → 내부 구조는 정렬될 수 있음

6. [4, 10]

• heap size(4) == d(4)
• heap.top() = 30 > 10 → 무시

7. [6, 5]

• heap size(4) < d(6) → push
• heap = [5, 40, 60, 50, 30] (MinHeap 구조 내부는 자동 유지됨)

---

문제

https://www.acmicpc.net/problem/14235

 

풀이

 

문제에서 선물을 줄 땐 가장 가치가 높은 선물을 준다라고 설정했기에 최대힙으로 설정했다.

 

문제 접근

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

  push(val) {
    this.heap.push(val);
    this.bubbleUp();
  }

  bubbleUp() {
    let idx = this.heap.length - 1;
    let val = this.heap[idx];

    while (idx > 0) {
      let parent = Math.floor((idx - 1) / 2);
      if (val <= this.heap[parent]) break;
      this.heap[idx] = this.heap[parent];
      idx = parent;
    }

    this.heap[idx] = val;
  }

  pop() {
    if (this.heap.length === 0) return -1;
    if (this.heap.length === 1) return this.heap.pop();

    const top = this.heap[0];
    const last = this.heap.pop();
    this.heap[0] = last;
    this.bubbleDown();
    return top;
  }

  bubbleDown() {
    let idx = 0;
    const len = this.heap.length;

    while (true) {
      let left = idx * 2 + 1;
      let right = idx * 2 + 2;
      let largest = idx;

      if (left < len && this.heap[left] > this.heap[largest]) {
        largest = left;
      }
      if (right < len && this.heap[right] > this.heap[largest]) {
        largest = right;
      }
      if (largest === idx) break;

      [this.heap[idx], this.heap[largest]] = [this.heap[largest], this.heap[idx]];
      idx = largest;
    }
  }
}

 

시행착오 - 조건문 실수

처음에 코드를 이렇게 작성했었다.

arr.forEach((v) => {
  if (v === 0) {
    result.push(heap.pop());
  } else {
    for (let i = 1; i <= v[0]; i++) {
      heap.push(v[i]);
    }
  }
});

이게 이상한 결과를 뱉는 것이었다. -1이 아니라 undefined, 혹은 아무것도 출력되지 않는 경우도 있었다.

 

문제는?

if (v === 0)

이 조건은 절대 true가 될 수 없다.
v는 문자열을 공백 기준으로 split한 배열이기 때문에, v === 0은 타입 자체가 다르다.

 

수정

let a = v[0];
if (a === 0) {
  result.push(heap.pop());
} else {
  for (let i = 1; i <= a; i++) {
    heap.push(v[i]);
  }
}

v[0]이 0인지 확인해야 의도한 분기 처리가 가능하다.
이 사소한 실수가 꽤 시간을 잡아먹었다.

 

최종 코드 (JavaScript)

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const input = fs.readFileSync(filePath).toString().trim().split('\n');

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

  push(v) {
    this.heap.push(v);
    this.bubbleUp();
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    let last = this.heap[index];

    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      if (last <= this.heap[parentIndex]) break;

      this.heap[index] = this.heap[parentIndex];
      index = parentIndex;
    }

    this.heap[index] = last;
  }

  pop() {
    if (this.heap.length === 0) return -1;
    if (this.heap.length === 1) return this.heap.pop();

    let top = this.heap[0];
    let last = this.heap.pop();
    this.heap[0] = last;
    this.bubbleDown();
    return top;
  }

  bubbleDown() {
    let index = 0;
    let length = this.heap.length;

    while (true) {
      let left = index * 2 + 1;
      let right = index * 2 + 2;
      let biggest = index;

      if (left < length && this.heap[left] > this.heap[biggest]) {
        biggest = left;
      }
      if (right < length && this.heap[right] > this.heap[biggest]) {
        biggest = right;
      }

      if (biggest === index) break;

      [this.heap[index], this.heap[biggest]] = [this.heap[biggest], this.heap[index]];
      index = biggest;
    }
  }
}

let n = +input[0];
let arr = input.slice(1).map((v) => v.split(' ').map(Number));
let result = [];
let heap = new MaxHeap();

arr.forEach((v) => {
  let a = v[0];

  if (a === 0) {
    result.push(heap.pop());
  } else {
    for (let i = 1; i <= a; i++) {
      heap.push(v[i]);
    }
  }
});

console.log(result.join('\n'));

 

이 문제를 풀면서 다음을 배웠다:

• 배열을 비교할 땐 ===를 조심하자. [0] === 0은 false다!
• 조건문에서 입력 형식을 정확히 파악하는 것이 시간 단축의 열쇠다.

---

문제

https://www.acmicpc.net/problem/23843

 

풀이

문제를 보면 전체 충전이 완료되는 최소 시간은 가장 늦게 끝나는 콘센트의 시간이다.

• 모든 기기를 병렬로 충전할 때, 총 소요되는 최소 시간은?

즉, M개의 작업 큐에 N개의 작업을 가장 잘 분배해서, 전체 작업이 끝나는 시간을 최소화하는 것이 목표.

 

처음 생각한 방식 (그리디 + 최대힙?)

하지만 여기서 놓친 포인트가 있다

• *가장 오래 걸리는 기기를 먼저 처리하는 게 중요한 게 아니다.
  가장 빨리 끝나는 콘센트를 찾아서, 그 콘센트에 다음 기기를 할당해야 전체 작업 시간을 줄일 수 있다.
• "기기 중 시간이 오래 걸리는 애부터 먼저 처리하면 되겠지!"라는 생각에, 기기 리스트를 내림차순 정렬해서 가장 오래 걸리는 걸 먼저 처리하고 싶었다.

최소힙(Min Heap)을 사용하는 이유

우리는 항상 가장 빨리 비는 콘센트를 찾아야 하므로, 콘센트들의 누적 충전 시간을 관리하는 데 최소힙이 적절하다.

최대힙을 쓰면, 가장 오래 걸리는 콘센트부터 꺼내게 되므로 오히려 병목을 유발하게 된다.

 

예제로 흐름 정리

입력:

5 2
1 4 4 8 1

정렬된 기기 시간: [8, 4, 4, 1, 1]

• 콘센트 상태 초기값: [0, 0] (두 개의 콘센트)
• 8 → 0에 더함 → [0, 8] → 정렬: [8, 0] → 다시 [0, 8]
• 4 → 0에 더함 → [4, 8]
• 4 → 4에 더함 → [8, 8]
• 1 → 8에 더함 → [8, 9]
• 1 → 8에 더함 → [9, 9]

최종적으로 모든 기기 충전이 끝난 시간은 max(9, 9) = 9이다.

 

그렇게 최종 코드에 최소힙을 추가한다.

그리고 최소힙을 이용한 로직을 만들어야 한다.

 

const heap = new MinHeap();
for (let i = 0; i < M; i++) heap.push(0);

먼저, M개의 콘센트가 있다고 했으니, 콘센트 각각의 현재 충전 누적 시간을 0으로 초기화해 최소힙에 넣는다.

• 이 최소힙은 결국 콘센트의 "현재까지의 총 충전 시간"을 관리하는 구조다.
• heap.pop()을 하면 가장 빨리 충전이 끝나는 콘센트를 꺼낼 수 있다.

for (let t of times) {
  let minTime = heap.pop();
  heap.push(minTime + t);
}

하나씩 기기를 순회하며 콘센트에 배정하는 핵심 부분이다.

• minTime = heap.pop()
  → 지금까지 누적 충전 시간이 가장 적은 콘센트를 꺼낸다.
• heap.push(minTime + t)
  → 그 콘센트에 새 기기의 충전 시간 t를 더한 값을 다시 힙에 넣는다.
  → 즉, 해당 콘센트는 minTime + t 시점까지 바쁘게 된다.

이 과정을 반복하면, 기기들은 항상 가장 빨리 끝나는 콘센트부터 순차적으로 채워진다.
그 결과, 병렬로 작동하는 콘센트 중 가장 늦게 끝나는 콘센트 시간이 전체 충전 시간이다.

 

console.log(heap.getMax());

마지막으로, 모든 기기 배정이 끝난 후 힙에 남아있는 값들 중 가장 큰 값이 바로 최종 충전 완료 시간이다.

• 이건 "가장 마지막까지 일한 콘센트"의 누적 충전 시간이다.
• 병렬 작업에서 최종 작업 완료 시간은 가장 늦게 끝난 작업의 종료 시간으로 결정되므로, max 값을 출력하면 된다.

전체 코드

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

  push(v) {
    this.heap.push(v);
    this.bubbleUp();
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    let last = this.heap[index];

    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);

      if (last >= this.heap[parentIndex]) break;
      this.heap[index] = this.heap[parentIndex];
      index = parentIndex;
    }

    this.heap[index] = last;
  }

  pop() {
    if (this.heap.length === 0) return 0;
    if (this.heap.length === 1) return this.heap.pop();

    let top = this.heap[0];
    let last = this.heap.pop();
    this.heap[0] = last;
    this.bubbleDown();
    return top;
  }

  bubbleDown() {
    let index = 0;
    let length = this.heap.length;

    while (true) {
      let left = index * 2 + 1;
      let right = index * 2 + 2;
      let smallest = index;

      if (left < length && this.heap[left] < this.heap[smallest]) {
        smallest = left;
      }
      if (right < length && this.heap[right] < this.heap[smallest]) {
        smallest = right;
      }

      if (index === smallest) break;
      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      index = smallest;
    }
  }

  getMax() {
    return Math.max(...this.heap);
  }
}

const [N, M] = input[0].split(' ').map(Number);
const times = input[1]
  .split(' ')
  .map(Number)
  .sort((a, b) => b - a);

const heap = new MinHeap();
for (let i = 0; i < M; i++) heap.push(0);

for (let t of times) {
  let minTime = heap.pop();
  heap.push(minTime + t);
}

console.log(heap.getMax());

---

문제

https://www.acmicpc.net/problem/5464

 

풀이

예제로 먼저 문제를 이해해보았다.

예제 1
1:200 2:100 3:300 4:800 차량 무게
1:2 2:3 3:5 주차자리 단위 무게

3이들어간다 빈자리2 2(1번자리)*300
2가들어간다 빈자리 1 2(1번자리)*300+3(2번자리)*100
-3이 나온다 빈자리 2
1이 들어간다 빈자리 1 번호가 작은 자리에 넣기 위해 +2(1번자리)*200
4가 들어간다 빈자리 0 +5(3번자리)*800
4가 나온다 빈자리 1
2가 나온다 빈자리 2
1이 나온다 빈자리 3


예제2
1:100 2:500 3:1000 4:2000 차량 무게
1:5 2:2 주차자리 단위 무게

3이 들어간다. 1번자리 5*1000 1:5:true 2:2:false
1이 들어간다. 2번자리 +2*100 1:5:true 2:2:true
2 자리가 없어 큐에 삽입
4 큐에 삽입
1이 나온다 1:5:false 2:2:true
큐가 비어있지 않아 2가 들어간다. 2번자리 +2*500 1:5:true 2:2:true
3이 나온다. 1:5:false 2:2:true
4가 들어간다. 1:5:true 2:2:true 1번 자리 5*2000
2가 나온다
4가 나온다

 

자리가 비면 가장 번호가 낮은 자리부터 채워야 한다는 점 때문에 최소힙을 이용했다.

 

처음엔 주차장을 그냥 배열로 만들고, 매번 parking.indexOf(null)을 사용해서 빈자리를 찾으려는 방법도 괜찮지 않을까 싶었지만,

// 틀린 접근
let idx = parking.indexOf(null);

이 방법은 효율도 안 좋고, 자리 번호가 빠르게 바뀔 경우에 관리가 어려웠다.

 

힙을 이용한 로직 설명은 주석으로 추가해 놨습니다.

let [n, m] = input[0].split(' ').map(Number);
let prices = input.slice(1, n + 1).map(Number);
let weights = input.slice(n + 1, n + m + 1).map(Number);
let orders = input.slice(n + m + 1).map(Number);

let parking = Array(n).fill(null); // n개의 주차 공간을 null로 초기화 (빈자리 표시)
let carToParking = Array(m + 1).fill(null); // 각 차량의 주차 위치를 기록할 배열 (1번 차량부터 시작하므로 m+1 크기)
let heap = new MinHeap();
let queue = [];
for (let i = 0; i < n; i++) heap.push(i); //처음엔 모두가 빈자리
let total = 0;

for (let ord of orders) {
  if (ord > 0) {
    //차량이 들어가야 한다면
    if (heap.size() > 0) {
      //빈자리가 있다면
      let spot = heap.pop(); //제일 번호가 작은 자리를 꺼냄
      parking[spot] = ord; // 해당 공간에 차량 번호를 기록
      carToParking[ord] = spot; // 차량 번호에 해당하는 주차 위치 저장
      total += prices[spot] * weights[ord - 1]; //해당 자리 가격*차량 무게
    } else {
      //빈자리가 없다면 대기 큐에 넣기
      queue.push(ord);
    }
  } else {
    //차량이 나와야 한다면
    let car = -ord; //차량번호 양수화
    let spot = carToParking[car]; //해당 자리 가져오기
    parking[spot] = null; //빈자리로 표시
    heap.push(spot); //빈자리 힙에 넣기기

    if (queue.length > 0) {
      //대기하는 차가 있다면
      let waitingCar = queue.shift(); //제일 앞에 있는 차 꺼냄
      let newSpot = heap.pop(); //빈자리 꺼냄
      parking[spot] = waitingCar;
      carToParking[waitingCar] = newSpot;
      total += prices[newSpot] * weights[waitingCar - 1];
    }
  }
}

console.log(total);

 

예시를 코드에 대입해 보며 바른 결과가 나오는지 확인해 보자.

 

각 데이터 의미

• n = 2 (주차 공간 수)
• m = 3 (차량 수)
• prices = [3, 2] → 자리 0의 단위 요금은 3, 자리 1의 단위 요금은 2
• weights = [200, 100, 300] → 1번 차 200kg, 2번 차 100kg, 3번 차 300kg
• orders = [1, 2, 3, -1, -2, -3]

초기상태

parking = [null, null];  // 두 자리 모두 비어 있음
carToParking = Array(4).fill(null);  // 차량 번호 1~3용
queue = []; // 대기 차량 없음
heap = MinHeap containing [0, 1]; // 자리 0, 1이 비어 있음
total = 0;

 

for (let ord of orders) 시작

 

ord = 1 (차량 1 입장)

• heap에 빈자리가 있음 → spot = 0 (자리 0 선택)
• parking [0] = 1
• carToParking [1] = 0
• 요금 계산: prices [0] * weights [0] = 3 * 200 = 600
• total = 600
• heap = [1] (자리 1만 남음)

ord = 2 (차량 2 입장)

• heap에 빈자리가 있음 → spot = 1
• parking [1] = 2
• carToParking [2] = 1
• 요금 계산: prices [1] * weights [1] = 2 * 100 = 200
• total = 800
• heap = [] (자리는 모두 찼음)

ord = 3 (차량 3 입장)

• heap이 비었음 → 대기 큐로
• queue = [3]

ord = -1 (차량 1 퇴장)

• car = 1, spot = carToParking [1] = 0
• parking [0] = null
• heap = [0] ← 자리 0이 비었음
• 대기 차량 있음 → waitingCar = 3
  • 자리 0에 넣음: parking[0] = 3
  • carToParking [3] = 0
  • 요금 계산: prices [0] * weights [2] = 3 * 300 = 900
  • total = 1700
• queue = []

ord = -2 (차량 2 퇴장)

• car = 2, spot = 1
• parking [1] = null
• heap = [1]
• queue = [] → 대기 차량 없음

ord = -3 (차량 3 퇴장)

• car = 3, spot = 0
• parking [0] = null
• heap = [0, 1]