백준_12764_싸지방에 간 준하

싸지방에 간 준하

문제

현재 대한민국 해군에 소속되어있는 준하는 문제를 풀기 위해 매일같이 사이버 지식 정보방 통칭 싸지방에 다닌다. 그러나 최근 문제가 생겼다. 싸지방에 사람이 몰려 컴퓨터 수가 모자라게 된 것이다. 이런 사태를 도저히 용납할 수 없었던 준하는 곧 전역하는 선임을 설득해 민원을 넣도록 하는 데 성공했다.

마침내 부대에서는 민원을 받아들이기로 하였고, 컴퓨터를 증설하기로 했다. 또한, 컴퓨터 간의 사용률에 따라 다른 성능의 컴퓨터를 설치하고자 한다.

하지만 예산이 부족해 사람 수 만큼 컴퓨터를 살 수가 없었다. 고심에 고심을 거듭한 준하는 모든 사람이 항상 정해진 시간에 싸지방을 이용한다는 사실을 발견했다.

컴퓨터가 있는 자리에는 1번부터 순서대로 번호가 매겨져 있다. 모든 사람은 싸지방에 들어왔을 때 비어있는 자리 중에서 번호가 가장 작은 자리에 앉는 것이 규칙이다.

준하가 발견한 사실과 이용 규칙을 가지고, 모든 사람이 기다리지 않고 싸지방을 이용할 수 있는 컴퓨터의 최소 개수와 자리별로 몇 명의 사람이 사용했는가를 구하시오.

입력

첫째 줄에 사람의 수를 나타내는 $N$이 주어진다. $(1 \le N \le 100,000)$ 둘째 줄부터 $N$개의 줄에 걸쳐서 각 사람의 컴퓨터 이용 시작 시각 $P$와 종료 시각 $Q$가 주어진다. $(0 \le P \lt Q \le 1,000,000)$

시작 시각이나 종료 시각이 다른 사람과 겹치는 경우는 없다.

출력

첫째 줄에 사람이 모든 사람이 기다리지 않아도 되는 컴퓨터의 최소 개수 $X$를 출력한다.
둘째 줄에는 1번 자리부터 $X$번 자리까지 순서대로 각 자리를 사용한 사람의 수를 띄어쓰기 간격으로 출력한다.

예제 입력 1

5
20 50
10 100
30 120
60 110
80 90

예제 출력 1

4
1 2 1 1

풀이 및 해설

출력값: 모든 사람이 기다리지 않고 싸지방 이용할 수 있는 컴퓨터의 최소개수와 자리별 이용 횟수 구하기

• 컴퓨터가 있는 자리에는 1번부터 순서대로 번호 매겨있음
• 싸지방 들어왔을 때 빈 자리 중 번호가 가장 작은 자리에 앉아야함

[우선순위 큐 이용]
1. 첫번째로 사용하는 사람이거나 들어온 사람의 시작시간이 큐의 맨 앞(이용 끝난 컴퓨터 중 가장 작은 번호)의 종료 시간보다 작은 경우 → 새로운 컴퓨터 추가 후 사람 정보(사용중인 컴퓨터 번호, 종료 시간) 배열에 넣기
2. 들어온 사람의 시작시간이 큐의 맨 앞의 종료시간보다 크거나 같은 경우 → 해당 컴퓨터 사용하고, 사람 정보 배열에 추가

Code

메모리초과 발생 → sort() 메서드 사용 X (직접 우선순위 큐 구현 해야함..)

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const N = +input[0]; // 사람의 수
const people = [];
const computers = []; // 사용한 컴퓨터 별 이용 횟수
const sortedQ = [];
let number = 0;
let index = 0;
for (let p = 1; p <= N; p++) {
  const [P, Q] = input[p].split(' ').map(Number); // P: 컴퓨터 이용 시작 시각, Q: 종료 시각
  people.push({ P: P, Q: Q });
}
people.sort((a, b) => a.P - b.P);

for (const p of people) {
  const { P, Q } = p;
  if (sortedQ.length && sortedQ[index].finish <= P) {
    computers[sortedQ[index++].num] += 1;
  } else {
    computers.push(1);
    number++;
  }
  sortedQ.push({ num: number, finish: Q });
  sortedQ.sort((a, b) => a.finish - b.finish);
}

console.log(number);
console.log(computers.join(' '));

---

우선순위 큐

우선순위 큐 JS 구현

• 이용 중인 컴퓨터 배열을 종료시간 기준 오름차순 정렬
• 이용이 끝난 컴퓨터 배열을 컴퓨터 번호 기준 오름차순 정렬

→ 총 2개의 우선순위 큐 필요!

class PriorityQueue {
  constructor() {
    this.heap = []; // 빈 배열 생성
  }

  getLeftChildIndex = (parentIndex) => parentIndex * 2 + 1; // 왼쪽 자식 인덱스
  getRightChildIndex = (parentIndex) => parentIndex * 2 + 2; // 오른쪽 자식 인덱스
  getParentIndex = (childIndex) => Math.floor((childIndex - 1) / 2); // 부모 인덱스

  peek = () => this.heap[0].key; // 루트 노드 반환
  size = () => this.heap.length; // heap 배열 크기 반환
  isEmpty = () => this.heap.length === 0;

  // 원소 삽입
  enqueue = (key, value) => {
    const node = { key, value };
    this.heap.push(node); // 새 원소 마지막 위치에 삽입
    this.heapifyUp(); // 정렬 수행
  };

  // 아래에서 위로 정렬
  heapifyUp = () => {
    let index = this.size() - 1; // 마지막 인덱스
    const lastNode = this.heap[index]; // 마지막 원소

    while (index > 0) {
      const parentIdx = this.getParentIndex(index); // 부모 인덱스 찾기
      // 부모 원소의 종료 시간이 자식 원소 종료시간보다 큰 경우 swap
      if (this.heap[parentIdx].key > lastNode.key) {
        this.heap[index] = this.heap[parentIdx];
        index = parentIdx;
      } else break;
    }
    this.heap[index] = lastNode; // 본인 자리 찾아가기
  };

  // 원소 삭제
  dequeue = () => {
    if (this.isEmpty()) return null; // 비어있는 경우 삭제 불가능

    const rootNode = this.heap[0];
    if (this.heap.length === 1) this.heap = [];
    else {
      this.heap[0] = this.heap.pop(); // 맨 마지막에 있는 원소 루트로 이동
      this.heapifyDown(); // 정렬 수행
    }
    return rootNode; // 루트 노드 반환
  };

  // 위에서 아래로 정렬
  heapifyDown = () => {
    let index = 0;
    const heapSize = this.size();
    const rootNode = this.heap[index];

    while (this.getLeftChildIndex(index) < heapSize) {
      const leftChildIdx = this.getLeftChildIndex(index); // 왼쪽 자식 인덱스
      const rightChildIdx = this.getRightChildIndex(index); // 오른쪽 자식 인덱스

      // 부모노드가 자식 노드들보다 값이 큰 경우 swap
      // 왼쪽 자식 노드와 오른쪽 자식 노드 중 더 작은 값을 가지는 인덱스와 부모 노드랑 변경
      const smallerChildIndex =
        rightChildIdx < heapSize &&
        this.heap[rightChildIdx].key < this.heap[leftChildIdx].key
          ? rightChildIdx
          : leftChildIdx;

      // 자식 노드 값이 부모 노드보다 작은 경우 swap
      if (this.heap[smallerChildIndex].key <= rootNode.key) {
        this.heap[index] = this.heap[smallerChildIndex];
        index = smallerChildIndex;
      } else break;
    }
    this.heap[index] = rootNode;
  };
}

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const N = +input[0]; // 사람의 수
const people = [];
for (let p = 1; p <= N; p++) {
  const [P, Q] = input[p].split(' ').map(Number); // P: 컴퓨터 이용 시작 시각, Q: 종료 시각
  people.push({ P: P, Q: Q });
}
people.sort((a, b) => a.P - b.P);

let number = 0;
const computers = [];
const usedComputers = new PriorityQueue(); // 사용 중인 컴퓨터
const unUsedComputers = new PriorityQueue(); // 사용이 끝난 컴퓨터
for (const p of people) {
  const { P, Q } = p;
  // 사용이 끝난 컴퓨터가 있는지 확인
  while (!usedComputers.isEmpty() && usedComputers.peek() <= P) {
    const { value: computerIdx } = usedComputers.dequeue(); // 끝난 컴퓨터 정보(종료시간, 컴퓨터 번호) 꺼내기
    unUsedComputers.enqueue(computerIdx, 0); // 사용 끝난 컴퓨터 저장 => 컴퓨터 번호 오름차순으로 정렬
  }

  // 사용이 끝난 컴퓨터가 있는 경우
  // 해당 컴퓨터 번호 이용
  if (!unUsedComputers.isEmpty()) {
    const { key: computerIdx } = unUsedComputers.dequeue();
    computers[computerIdx] += 1; // 해당 컴퓨터 이용 횟수 추가
    usedComputers.enqueue(Q, computerIdx); // 다시 이용중인 컴퓨터로 변경
  }
  // 사용이 끝난 컴퓨터가 없는 경우
  // 새로운 컴퓨터 추가
  else {
    usedComputers.enqueue(Q, number);
    computers.push(1);
    number++;
  }
}

console.log(number);
console.log(computers.join(' '));