[백준] 14235 크리스마스 선물 JavaScript

혅·2024년 4월 28일

백준, 프로그래머스 -JavaScript-

목록 보기

87/215

문제

크리스마스에는 산타가 착한 아이들에게 선물을 나눠준다. 올해도 산타는 선물을 나눠주기 위해 많은 노력을 하고 있는데, 전세계를 돌아댕기며 착한 아이들에게 선물을 나눠줄 것이다. 하지만 산타의 썰매는 그렇게 크지 않기 때문에, 세계 곳곳에 거점들을 세워 그 곳을 방문하며 선물을 충전해 나갈 것이다. 또한, 착한 아이들을 만날 때마다 자신이 들고있는 가장 가치가 큰 선물 하나를 선물해 줄 것이다.

이제 산타가 선물을 나눠줄 것이다. 차례대로 방문한 아이들과 거점지의 정보들이 주어졌을 때, 아이들이 준 선물들의 가치들을 출력하시오. 만약 아이들에게 줄 선물이 없다면 -1을 출력하시오.

입력

첫 번째 줄에서는 아이들과 거점지를 방문한 횟수 n이 주어진다.(1≤n≤5,000)

다음 n줄에는 a가 들어오고, 그 다음 a개의 숫자가 들어온다. 이는 거점지에서 a개의 선물을 충전하는 것이고, 그 숫자들이 선물의 가치이다. 만약 a가 0이라면 거점지가 아닌 아이들을 만난 것이다. 선물의 가치는 100,000보다 작은 양의 정수이다.(1≤a≤100)

출력

a가 0일 때마다, 아이들에게 준 선물의 가치를 출력하시오. 만약 줄 선물이 없다면 -1을 출력하라. 적어도 하나의 출력이 있음을 보장한다.

예제 입력

5
0
2 3 2
0
0
0

예제 출력

-1
3
2
-1

내가 했던 풀이 방법

※ 해당 문제는 Priority Queue를 이용하여 풀이하였으며, Priority Queue 구현은 [JS] 우선순위 큐 (Priority Queue)를 참고하여 구현했습니다.

class를 이용해 우선순위 큐를 구현해주고, answer은 빈 배열로 초기화해준다.
input[i]을 공백으로 분할한 값 중 첫번째 값이 0일 경우, heap의 크기가 1일 경우에는 -1을, 1이 아닐 경우에는 heap에서 최대값을 제거해준 값을 answer에 넣어준다.
첫 번째 값이 0이 아닐 경우, 1부터 첫 번째 값까지 반복하며, input[i]에 있는 값들을 heap에 추가해준다. (이때, 첫 번째 값은 개수를 의미할 뿐 추가해주지 않는 것에 주의한다.)
2-3번을 n번 반복한 뒤, answer에 있는 값들을 한 줄씩 출력해준다.

코드

const fs = require('fs');
let [n, ...input] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

n = Number(n.trim());
class Maxheap {
  constructor() {
    this.heap = [null];
  }

  add(value) {
    this.heap.push(value);
    let currentIndex = this.heap.length - 1;
    let parentIndex = Math.floor(currentIndex / 2);
    while (parentIndex !== 0 && this.heap[parentIndex] < value) {
      [this.heap[parentIndex], this.heap[currentIndex]] = [this.heap[currentIndex], this.heap[parentIndex]];
      currentIndex = parentIndex;
      parentIndex = Math.floor(currentIndex / 2);
    }
  }

  remove() {
    if (this.heap.length === 2) return this.heap.pop();
    let value = this.heap[1];
    this.heap[1] = this.heap.pop();
    let currentIndex = 1;
    let left = 2;
    let right = 3;
    while (this.heap[currentIndex] < this.heap[left] || this.heap[currentIndex] < this.heap[right]) {
      if (this.heap[left] < this.heap[right]) {
        [this.heap[currentIndex], this.heap[right]] = [this.heap[right], this.heap[currentIndex]];
        currentIndex = right;
      } else {
        [this.heap[currentIndex], this.heap[left]] = [this.heap[left], this.heap[currentIndex]];
        currentIndex = left;
      }
      left = currentIndex * 2;
      right = left + 1;
    }
    return value;
  }

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

let heap = new Maxheap();
let answer = [];
for (let i = 0; i < n; i++) {
  input[i] = input[i].trim().split(' ').map(Number);
  if (input[i][0] === 0) {
    if (heap.size() === 1) {
      answer.push(-1);
    } else {
      answer.push(heap.remove());
    }
  } else {
    for (let j = 1; j <= input[i][0]; j++) {
      heap.add(input[i][j]);
    }
  }
}

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

회고

우선순위 큐를 구현하면 다른 구현은 어렵지 않은 문제였다. 처음에는 문제에서 제시한 그대로 구현도 해보고, 정렬을 해보기도 했는데 시간초과에 걸려 확인해보니 우선순위 큐를 이용해 풀이해주는 문제였다. 분명 우선순위 큐를 알긴하는데 정확하게 무엇이다!라고 떠오르지가 않아서 이 문제를 그냥 풀이하는 것보다 우선순위 큐/힙을 공부한 뒤에 풀어보자 생각해서 공부를 한 뒤에 다시 풀었다. MaxHeap 구현에 문제가 있어서 굉장히 오래.. 풀이하긴 했지만 ~~(중간에 멘탈 한 번 뒤집어졌다.)~~ 그래도 우선순위 큐에 대해서 다시 정리하고 갈 수 있었던 것 같다.

힙

완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
힙은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다. 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다. 즉, 부모노드와 서브트리간 대소 관계가 성립된다.
이진탐색트리(BST)와 달리 중복된 값이 허용된다.

최대 힙 (Max Heap)
부모 노드의 키 값이 자식 노드보다 크거나 같은 완전이진트리이다.

최소 힙 (Min Heap)
부모 노드의 키 값이 자식 노드보다 작거나 같은 완전이진트리이다.

힙을 저장하는 표준적인 자료구조는 배열이다. 완전 이진트리이므로 중간에 비어있는 요소가 없기 때문이다. 구현을 쉽게 하기 위해 배열의 첫 번째 인덱스인 0은 사용되지 않는다.

특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다. 간단히 말해, 루트 노드의 오른쪽 노드의 번호는 항상 3이다.

힙의 특징
왼쪽 자식의 인덱스 = (부모의 인덱스) 2
오른쪽 자식의 인덱스 = (부모의 인덱스) 2 + 1
부모의 인덱스 = (자식의 인덱스) / 2

다음은 heap에 데이터를 추가하고 삭제하는 방법이다. 아래에서 사용된 방법은 Max Heap 기준이다.

우선순위 큐

큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이지만, 우선순위 큐는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.

우선순위 큐는 일반적으로 힙(Heap)을 이용하여 구현한다.