문제

시내 주차장은 1부터 N까지 번호가 매겨진 N개의 주차 공간을 가지고 있다. 이 주차장은 매일 아침 모든 주차 공간이 비어 있는 상태에서 영업을 시작하며, 하룻동안 다음과 같은 방식으로 운영된다. 차가 주차장에 도착하면, 주차장 관리인이 비어있는 주차 공간이 있는지를 검사한다. 만일 비어있는 공간이 없으면, 차량을 빈 공간이 생길 때까지 입구에서 기다리게 한다. 만일 빈 주차 공간이 하나만 있거나 또는 빈 주차 공간이 없다가 한 대의 차량이 주차장을 떠나면 곧바로 그 장소에 주차를 하게 한다. 만일 빈 주차 공간이 여러 곳이 있으면, 그 중 번호가 가장 작은 주차 공간에 주차하도록 한다. 만일 주차장에 여러 대의 차량이 도착하면, 일단 도착한 순서대로 입구의 대기장소에서 줄을 서서 기다려야 한다. 대기장소는 큐(queue)와 같이, 먼저 대기한 차량부터 주차한다.

주차료는 주차한 시간이 아닌 차량의 무게에 비례하는 방식으로 책정된다. 주차료는 차랑의 무게에다 주차 공간마다 따로 책정된 단위 무게당 요금을 곱한 가격이다.

주차장 관리원은 오늘 M대의 차량이 주차장을 이용할 것이라는 것을 알고 있다. 또한, 차량들이 들어오고 나가는 순서도 알고 있다.

주차 공간별 요금과 차량들의 무게와 출입 순서가 주어질 때, 오늘 하룻동안 주차장이 벌어들일 총 수입을 계산하는 프로그램을 작성하라.

입력

반드시 표준 입력으로부터 다음의 데이터를 읽어야 한다.

첫 번째 줄에는 정수 N과 M이 빈칸을 사이에 두고 주어진다.
그 다음 N개의 줄에는 주차 공간들의 단위 무게당 요금을 나타내는 정수들이 주어진다. 그 중 s번째 줄에는 주차 공간 s의 단위 무게당 요금 Rs가 들어있다.
그 다음 M개의 줄에는 차량들의 무게를 나타내는 정수들이 주어진다. 차량들은 1 부터 M 까지 번호로 구분되고, 이 번호는 출입 순서와는 상관없다. 이 M개의 줄 중 k번째 줄에는 차량 k의 무게를 나타내는 정수 Wk가 들어있다.
그 다음 2*M 개의 줄에는 차량들의 주차장 출입 순서를 나타내는 정수들이 한 줄에 하나씩 주어진다. 양의 정수 i는 차량 i가 주차장에 들어오는 것을 의미하고, 음의 정수 -i는 차량 i가 주차장에서 나가는 것을 의미한다. 주차장에 들어오지 않은 차량이 주차장에서 나가는 경우는 없다. 1 번부터 M 번까지 모든 차량은 정확하게 한 번씩 주차장에 들어오고, 한 번씩 주차장에서 나간다. 또한 입구에서 대기 중인 차량이 주차를 하지 못하고 나가는 경우는 없다.
1 ≤ N ≤ 100 주차 공간의 수
1 ≤ M ≤ 2,000 차량의 수
1 ≤ Rs ≤ 100 주차 공간 s의 단위 무게당 요금
1 ≤ Wk ≤ 10,000 차량 k의 무게

출력

출력은 반드시 표준 출력으로 하여야 하며, 하나의 줄에 한 개의 정수를 출력한다. 이 정수는 오늘 하룻동안 주차장이 벌어들인 총 수입이다.

예제 입력

3 4
2
3
5
200
100
300
800
3
2
-3
1
4
-4
-2
-1

예제 출력

5300

내가 했던 풀이 방법

문제를 간단하게 요약하자면, 차량이 입력대로 들어올거고 요금은 머무는 시간 등과 관련없이 단순히 차의 무게*주차한 위치의 요금으로만 판단한다. 그리고 주차한 위치는 비어있는 공간 중에 가장 번호가 낮은 공간에 우선적으로 배치된다. (최대/최소를 찾는 게 아닌 이 규칙대로 했을 때의 요금)

입력에 맞춰 price, weight, order를 저장하고 최소 힙(우선순위 큐) 클래스를 구현해주었다. 사실 우선순위 큐를 풀기 위해 선택한 문제라 우선순위 큐로 풀었는데 JS는 우선순위 큐 구현이 번거로우니 다른 방법으로 풀어도 될 듯 하다. 구현해보진 않았으나 필수는 아닐 것 같다. (이마저도 다소 비효율적으로 구현한 듯 하다.)

일반적인 우선순위 큐를 구현하되 초기화 부분을 다르게 두었다. 보편적으로는 0번째를 null로 둔 배열로 시작하지만, 여기서는 1부터 N만큼을 넣어준 배열로 초기화를 해준다. 예를 들어 N이 3이라면 [null, 1, 2, 3]이 초기값이 되는 것이다.
이렇게 한 이유는 우선순위 큐를 현재 주차 가능한 구역 번호를 다루는 것으로 활용할 것이기 때문이다. 즉, dequeue로 반환되는 값은 이번에 주차될 구역 번호가 되는 것이다.

추가적으로 2개의 배열이 필요한데, wait와 parked이다. wait는 대기큐로 만약 자리가 없을 경우, 무한정 대기라고 했으니 대기를 하는 차 번호를 넣어줄 것이고 parked는 주차를 한다면, 그 구역을 기억해두어야 한다. 그걸 위해 M+1 크기로 초기화해주었다. null일 경우에는 해당 차는 주차 중이지 않다라는 걸 의미한다. (문제에서 오류 상황이 없다고 해주었기 때문에 이렇게 두어도 안전하다.)

order 순서대로 주차 시뮬을 돌리면 해당 수가 음수일 때, 양수일 때로 case가 나뉜다. 양수일 때는 차가 주차하러 들어오는 것이다. 이때, 주차 공간이 없을 경우, peek()의 반환값이 null이다. 그럴경우에는 wait에 해당 차를 push 해주면 된다. 주차 공간이 있을 경우, 주차할 위치를 dequeue로 받아온다. parked에 해당 차 위치에 dequeue의 반환값을 넣어준다. (=order[i]의 차가 dequeue() 구역에 주차됨) 그리고 요금을 계산하기 위해 price와 weight를 이용해준다. 이때 price와 weight는 0번째 index가 시작 기준이므로 -1을 해주어야 함에 유의한다.

order[i]가 음수일 경우, 차가 주차장에서 나간다. 이 경우, 해당 차가 위치된 구역을 parked를 통해 받아오고, 해당 위치를 null로 바꿔준다. (오류가 없으므로 이 과정을 무시해도 오류는 나지 않겠지만, 안전하게 하기 위해) 주차 중이던 구역이 이제 다시 이용 가능해졌으므로 enqueue를 통해 해당 구역을 추가해준다.
만약, wait의 length가 0보다 크다면, 대기중인 차가 있다는 의미이다. 차가 나감과 동시에 가장 먼저온 차가 주차를 할 수 있게 된다 했으므로, wait의 0번째 차를 enter처리 해준다. enter처리는 위에서 진행했던 방식과 동일하다.

모든 order[i]를 처리하고 나면 total에 요금이 계산되게 된다.

코드

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

let [N, M] = n.trim().split(' ').map(Number);
let price = input.slice(0, N).map(Number);
let weight = input.slice(N, N + M).map(Number);
let order = input.slice(N + M).map(Number);

class MinHeap {
  constructor(size) {
    this.heap = [null];
    for (let i = 1; i <= size; i++) {
      this.enqueue(i);
    }
  }

  enqueue(value) {
    this.heap.push(value);
    let current = this.heap.length - 1;
    let parent = Math.floor(current / 2);

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

  dequeue() {
    if (this.heap.length === 1) return null;
    else if (this.heap.length === 2) return this.heap.pop();

    let value = this.heap[1];
    this.heap[1] = this.heap.pop();
    let current = 1;

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

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

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

    return value;
  }

  peek() {
    if (this.heap.length === 1) return null;
    else return this.heap[1];
  }
}

let park = new MinHeap(N);
let wait = [];
let parked = Array.from({ length: M + 1 }, () => null);
let total = 0;
for (let i = 0; i < order.length; i++) {
  if (order[i] < 0) {
    //leave
    let num = parked[Math.abs(order[i])];
    parked[Math.abs(order[i])] = null;
    park.enqueue(num);
    if (wait.length) {
      let car = wait.shift();
      let num = park.dequeue();
      parked[car] = num;
      total += price[num - 1] * weight[car - 1];
    }
  } else {
    //enter
    if (park.peek() === null) {
      wait.push(order[i]);
    } else {
      let num = park.dequeue();
      parked[order[i]] = num;
      total += price[num - 1] * weight[order[i] - 1];
    }
  }
}

console.log(total);

회고

백준 문제를 한 달...? 넘게 안 풀었더니 뇌가 굳어서 유일하게 풀 암기를 해두었던 우선순위 큐 구현 코드를 기억해내려고 우선순위 큐로 접근했더니 생각보다 복잡하게 풀이했던 것 같다. 더 단순하게 풀면 쉬웠을 것...? 같기도 하고 제한이 그렇게 타이트하지 않아서 다행히 열심히 암기를 했던 탓에 오랫동안 백준 풀기도 했고... 우선순위 큐는 까먹지 않아서 다행이다. 그렇게 어려운 문제는 아니였는데 입력 처리가 사알짝 귀찮고 우선순위 큐 클래스 구현하는 것도 귀찮고 해서 살짝 시간 쓰긴 했다. 우선순위 큐라는 특성 상 실버2인 것 같긴한데 개인적으로는 그 이하 정도여도 괜찮을 문제.