[백준] 2109 순회강연 - javascript

📌 문제

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

📌 풀이

class minHeap {
  constructor() {
    this.heap = [];
    this.heap.push(-Infinity);
  }
  insert(val) {
    this.heap.push(val); 
    this.upheap(this.heap.length - 1); 
  }
  upheap(pos) {
    let tmp = this.heap[pos]; 
    while (tmp < this.heap[parseInt(pos / 2)]) {
      this.heap[pos] = this.heap[parseInt(pos / 2)];
      pos = parseInt(pos / 2); 
    }
    this.heap[pos] = tmp; 
  }
  get() {
    if (this.heap.length === 2) return this.heap.pop();
    let res = this.heap[1];
    this.heap[1] = this.heap.pop(); 
    this.downheap(1, this.heap.length - 1);
    return res; 
  }
  downheap(pos, len) {
    let tmp = this.heap[pos],
      child;
    while (pos <= parseInt(len / 2)) {
      child = pos * 2;
      if (child < len && this.heap[child] > this.heap[child + 1]) child++;
      if (tmp <= this.heap[child]) break;
      this.heap[pos] = this.heap[child]; 
      pos = child;
    }
    this.heap[pos] = tmp;
  }
  size() {
    return this.heap.length - 1;
  }
  front() {
    return this.heap[1];
  }
}

let input = require("fs").readFileSync("/dev/stdin").toString().split("\n");
let n = Number(input[0]);
if (n === 0) {
  console.log(0);
  return 0;
}
let arr = new Array(n);
let pq = new minHeap();
let time = 0;
let ans = 0;
for (let i = 0; i < arr.length; i++) {
  arr[i] = new Array(2);
}
for (let i = 0; i < n; i++) {
  arr[i][0] = Number(input[i + 1].split(" ")[0]);
  arr[i][1] = Number(input[i + 1].split(" ")[1]);
}
arr.sort((a, b) => a[1] - b[1]);

time = 1;
pq.insert(arr[0][0]);
for (let i = 1; i < arr.length; i++) {
  if (time < arr[i][1]) {
    pq.insert(arr[i][0]);
    time++;
  } else {
    if (pq.front() < arr[i][0]) {
      pq.get();
      pq.insert(arr[i][0]);
    }
  }
}
let pq_size = pq.size();
for (let i = 0; i < pq_size; i++) {
  ans += pq.get();
}
console.log(ans);

✔ 알고리즘 : 우선순위 큐를 사용한 그리디

✔ 자바스크립트에는 heap을 통해 우선순위 큐를 구현

✔ 우선 deadline기준으로 오름차순 정렬

✔ time을 1로 설정하고 minheap으로 구현한 우선순위 큐에 정렬된 첫번째 강연의 강연료를 insert

✔ for문으로 강연을 돌면서 현재 시간보다 다음 강연의 deadline이 크면 우선순위 큐에 집어넣고 시간을 1증가

✔ 만약 다음강연의 deadline이 현재 time보다 작으면 우선순위큐의 상단값(minheap이기 때문에 최솟값 = 현재 진행한 강연중 강연료가 제일 낮은 강연)과 비교하여 강연료가 높으면 우선순위큐에서 pop하고 현재 탐색중인 강연을 insert

✔ 마지막에 우선순위 큐에 남아있는 강연의 강연료들의 합이 최대로 벌 수 있는 돈이므로 ans에 저장

❗ 주의할 점
만약 강연이 하나도없는 경우 n은 0이다. 여기서 예외처리를 안해주면 백준에서 런타임에러가 발생하므로 강연이 하나도 안들어오는 경우 예외처리를 하여 0을 return해줘야 한다

✔ 난이도 : 백준 기준 골드 3