[백준 1715 - Node.js] 카드 정렬하기

🔗 문제 링크

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

1715번: 카드 정렬하기

✏️ 풀이

class PriorityQueue {
  constructor() {
    this.heap = [];
  }
    
  swap(a, b) {
      const temp = this.heap[a];
      this.heap[a] = this.heap[b];
      this.heap[b] = temp;
  }

  push(value) {
    const { heap } = this;
    heap.push(value);
    let index = heap.length - 1;
    let parent = Math.floor((index - 1) / 2);

    while (index > 0 && heap[index] < heap[parent]) {
      this.swap(index, parent);
      index = parent;
      parent = Math.floor((index - 1) / 2);
    }
  }

  pop() {
    const { heap } = this;
    if (heap.length <= 1) {
      return heap.pop();
    }

    const output = heap[0];
    heap[0] = heap.pop();
    let index = 0;

    while (index * 2 + 1 < heap.length) {
      let left = index * 2 + 1;
      let right = index * 2 + 2;
      let next = index;

      if (heap[left] < heap[next]) {
        next = left;
      }

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

      if (index === next) {
        break;
      }

      this.swap(index, next);
      index = next;
    }

    return output;
  }
}

const [N, ...cards] = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n')
  .map(Number);
const queue = new PriorityQueue();
let count = 0;

cards.forEach(card => {
  queue.push(card);
});

while (queue.heap.length > 1) {
  const sum = queue.pop() + queue.pop();
  queue.push(sum);
  count += sum;
}

console.log(count);

카드 묶음을 합칠 때마다 카드 수가 누적되므로, 최대한 카드 수가 적은 묶음끼리 합쳐야 한다. 전체 카드 묶음 중에서 가장 카드 수가 적은 두 묶음을 합치는 과정을 반복하면 최소한의 비교로 카드를 합칠 수 있다.

 

두 카드 묶음을 합치고 나서, 이 카드 묶음을 포함한 전체 카드 묶음 중에서 계속해서 카드 수가 적은 두 묶음을 찾아내야 하므로 최소힙으로 구현한 우선순위 큐를 활용하여 큐의 가장 상단에서 두 묶음을 빼서 합치고 합친 카드 묶음을 다시 큐에 넣는 과정을 반복하였다. 그리고 큐에 넣은 카드 묶음의 수만큼을 count에 누적하여 전체 비교 횟수를 구할 수 있다.

 

우선순위 큐를 구현할 때 swap하는 과정을 비구조화 할당을 통해 [heap[index], heap[parent]] = [heap[parent], heap[index]]와 같이 표현할 수도 있지만 이렇게 하면 백준에서 수행 시간이 약 1.5배 더 증가하기 때문에 temp 변수를 만들어서 swap하는 방식으로 구현하였다.