문제 링크
https://www.acmicpc.net/problem/12764
풀이
문제에서 최종적으로 원하는 것은 필요한 컴퓨터의 최소 개수와 각 컴퓨터에 대한 사용 빈도 이다.
의사 코드 진행
- 입력 데이터를 시작 시간 기준으로 올림차순으로 정렬을 해준다.(시작 시간 순으로 데이터를 처리하기 위해서)
- 입력 데이터를 순회를 한다.
- 해당 순서의 데이터에서 시작 시간보다 종료 시간이 앞에 있는 사람들의 컴퓨터를 종료하고 해당 컴퓨터 번호를 저장한다.
- 저장된 컴퓨터 번호가 있다면 가장 작은 번호를 받아서 컴퓨터 사용을 시작한다.
- 저장된 번호가 없다면 새로운 컴퓨터를 추가해서 사용을 시작한다.
- 사용을 시작할때 해당 번호에 대해서 사용 기록을 저장한다.
필요한 것
- 입력 순서와 상관없이 종류 시간 순서대로 해당 컴퓨터의 번호를 알 수 있어야 한다.
- 종료된 순서와 상관없이 비어 있는 컴퓨터의 번호를 오름차순으로 알 수 있어야 한다.
이 두가지 모두 우선순위 큐를 사용하면 알수있는 것들이다.
코드
/*
모든 사람이 정해진 시간에 싸지방 이용
컴퓨터는 번호가 매겨져있다.
비어있는 컴이 있다면 낮은 번호를 먼저 사용
사람들이 기다리지 않고 싸지방을 이용할 수 있는 컴퓨터 최소의 개수와
각 자리의 사용 빈도
pc 자리는 우선 순위 큐로 시작 시간 순으로 들어와서,
끝나는 시간으로 나온다.
pc 번호를 어떻게 추적?
입장시 번호표를 들고 들어간다. 해당 번호 카운트
나올때 반납, 번호표 저장소도 우선 순위 큐
pc자리 우선 순위 큐는 끝나는 시간과 해당 컴 번호를 알고 있으면 된다.
번호표 저장소는 번호만
*/
//비어있는 컴퓨터 번호를 저장하기 위한 heap,
class MinHeap{
constructor(){
//index를 편하게다루기위해서 0번에 null을 넣어준다.
this.heap=[null];
}
//두 index의 저장된 값을 바꾸기 위한 함수
swap(a,b){
[this.heap[a], this.heap[b]]=[this.heap[b], this.heap[a]];
}
//데이터 저장
insert(value){
this.heap.push(value);
let currentIdx=this.heap.length-1;
let parentIdx=Math.floor(currentIdx/2);
while(parentIdx !== 0 && this.heap[parentIdx]>value){
this.swap(currentIdx, parentIdx);
currentIdx=parentIdx;
parentIdx=Math.floor(currentIdx/2);
}
}
//데이터 반환
extract(){
if(this.heap.length===1)return null;
if(this.heap.length===2)return this.heap.pop();
const returnValue=this.heap[1];
this.heap[1]=this.heap.pop();
let currentIdx=1;
let leftIdx=2;
let rightIdx=3;
//rightIdx의 값이 undefined인 경우도 있다. 이 부분 주의
while(
(this.heap[rightIdx] && this.heap[currentIdx] > this.heap[rightIdx] )||
(this.heap[leftIdx] && this.heap[currentIdx] > this.heap[leftIdx])
){
if(this.heap[rightIdx]===undefined || this.heap[leftIdx]<this.heap[rightIdx] ){
this.swap(leftIdx, currentIdx);
currentIdx=leftIdx;
}else{
this.swap(rightIdx, currentIdx);
currentIdx=rightIdx;
}
leftIdx=currentIdx*2;
rightIdx=leftIdx+1;
}
return returnValue;
}
// 길이가 1이면 null만 남은것,
isEmpty(){
return this.heap.length===1;
}
}
//컴퓨터 종료시간, 해당 컴퓨터 번호를 저장하기 위한 heap
class TimeMinHeap{
constructor(){
//[끝나는 시간, 컴 번호]의 형식으로 들어올거다.
this.heap=[null];
}
swap(a,b){
[this.heap[a], this.heap[b]]=[this.heap[b], this.heap[a]];
}
insert(value){
this.heap.push(value);
let currentIdx=this.heap.length-1;
let parentIdx=Math.floor(currentIdx/2);
while(parentIdx !== 0 && this.heap[parentIdx][0]>value[0]){
this.swap(currentIdx, parentIdx);
currentIdx=parentIdx;
parentIdx=Math.floor(currentIdx/2);
}
}
extract(){
if(this.heap.length===1)return null;
if(this.heap.length===2)return this.heap.pop();
const returnValue=[...this.heap[1]];
this.heap[1]=this.heap.pop();
let currentIdx=1;
let leftIdx=2;
let rightIdx=3;
while(
(this.heap[rightIdx] && this.heap[currentIdx][0] > this.heap[rightIdx][0] )||
(this.heap[leftIdx] && this.heap[currentIdx][0] > this.heap[leftIdx][0])
){
if(this.heap[rightIdx]===undefined || this.heap[leftIdx][0]<this.heap[rightIdx][0]){
this.swap(leftIdx, currentIdx);
currentIdx=leftIdx;
}else{
this.swap(rightIdx, currentIdx);
currentIdx=rightIdx;
}
leftIdx=currentIdx*2;
rightIdx=leftIdx+1;
}
return returnValue;
}
top(){
return this.heap[1];
}
size(){
return this.heap.length-1;
}
isEmpty(){
return this.heap.length===1;
}
}
const fs= require('fs');
const filePath=process.platform==='linux'?'/dev/stdin':'./input.txt';
const [N, ...S]=fs.readFileSync(filePath).toString().trim().split("\n");
const n=Number(N);
//입력 데이터 시작 시간순으로 정렬
const l=S.map(i=>i.split(' ').map(Number)).sort((a,b)=>a[0]-b[0]);
const numberHeap=new MinHeap();
const timeHeap= new TimeMinHeap();
//컴퓨터 번호로 사용될 변수
let idx=1;
//각 번호의 사용 빈도 저장을 위한 객체
const frequency={};
//입력값 순회
for(const [startTime,endTime] of l){
//현재 시작 시간보다 작은 종료시간들은 다 종료하고 컴퓨터 번호를 저장한다.
while(!timeHeap.isEmpty() && timeHeap.top()[0]< startTime){
const [e, comIdx]=timeHeap.extract();
numberHeap.insert(comIdx);
}
//저장된 컴퓨터 번호가 있다면 꺼내서 사용하고, 사용빈도도 올려준다.
if(!numberHeap.isEmpty()){
const i=numberHeap.extract();
frequency[i]++;
timeHeap.insert([endTime, i]);
continue
}else{
//저장된 번호가 없다면 새로운 컴퓨터를 추가하고, 사용빈도 객체에도 해당 번호를 추가해준다.
frequency[idx]=1;
timeHeap.insert([endTime,idx]);
idx++;
}
}
//결과값 출력
console.log(Object.keys(frequency).length +"\n"+Object.values(frequency).join(' '))
나는 큐에 저장되는 값이 다르다고 생각해서 큐를 두 가지 만들어서 사용했다. 하지만 다른 분들의 코드를 보니 node라는 클래스를 만들어서 저장되는 값을 관리하고, 큐는 하나로 사용을 했다.이 방식이 추상화가 더 잘 적용되었고 속도면에서도 더 좋다.굳이 큐를 두개씩이나 만든 부분이 아쉽다😿 너무 느리기도 하고😿 코드도 더 많고😿
/*
모든 사람이 정해진 시간에 싸지방 이용
컴퓨터는 번호가 매겨져있다.
비어있는 컴이 있다면 낮은 번호를 먼저 사용
사람들이 기다리지 않고 싸지방을 이용할 수 있는 컴퓨터 최소의 개수와
각 자리의 사용 빈도
pc 자리는 우선 순위 큐로 시작 시간 순으로 들어와서,
끝나는 시간으로 나온다.
pc 번호를 어떻게 추적?
입장시 번호표를 들고 들어간다. 해당 번호 카운트
나올때 반납, 번호표 저장소도 우선 순위 큐
pc자리 우선 순위 큐는 끝나는 시간과 해당 컴 번호를 알고 있으면 된다.
번호표 저장소는 번호만
*/
//단순 pc번호 우선순위큐를 위한 Node;
class NumberNode{
constructor(value){
this.data=value;
this.priority=value;
}
}
// pc 자리 우선순위 Node 는 value로 [끝 나는 시간, 컴 번호 ]
class ComNode{
constructor(value){
this.data=value;
this.priority = value[0];
}
}
class MinHeap{
constructor(){
this.heap=[null];
}
swap(a,b){
[this.heap[a], this.heap[b]]=[this.heap[b], this.heap[a]];
}
//insert시 노드가 들어올거다
insert(value){
this.heap.push(value);
let currentIdx=this.heap.length-1;
let parentIdx=Math.floor(currentIdx/2);
while(parentIdx !== 0 && this.heap[parentIdx].priority>value.priority){
this.swap(currentIdx, parentIdx);
currentIdx=parentIdx;
parentIdx=Math.floor(currentIdx/2);
}
}
extract(){
if(this.heap.length===1)return null;
if(this.heap.length===2)return this.heap.pop();
const returnValue=this.heap[1];
this.heap[1]=this.heap.pop();
let currentIdx=1;
let leftIdx=2;
let rightIdx=3;
while(
(this.heap[rightIdx] && this.heap[currentIdx].priority > this.heap[rightIdx].priority )||
(this.heap[leftIdx] && this.heap[currentIdx].priority > this.heap[leftIdx].priority)
){
if(this.heap[rightIdx]===undefined || this.heap[leftIdx].priority<this.heap[rightIdx].priority ){
this.swap(leftIdx, currentIdx);
currentIdx=leftIdx;
}else{
this.swap(rightIdx, currentIdx);
currentIdx=rightIdx;
}
leftIdx=currentIdx*2;
rightIdx=leftIdx+1;
}
return returnValue;
}
top(){
return this.heap[1];
}
size(){
return this.heap.length-1;
}
isEmpty(){
return this.heap.length===1;
}
}
const fs= require('fs');
const filePath=process.platform==='linux'?'/dev/stdin':'./input.txt';
const [N, ...S]=fs.readFileSync(filePath).toString().trim().split("\n");
const n=Number(N);
const l=S.map(i=>i.split(' ').map(Number)).sort((a,b)=>a[0]-b[0]);
const numberHeap=new MinHeap();
const timeHeap=new MinHeap();
let idx=1;
const frequency={};
for(const [startTime,endTime] of l){
//timeHeap에서 startTime보다 작다면 다 꺼내서 번호 저장소에 넣어준다.
while(!timeHeap.isEmpty() && timeHeap.top().priority< startTime){
const [e, comIdx]=timeHeap.extract().data;
const numbNode=new NumberNode(comIdx);
numberHeap.insert(numbNode);
}
if(!numberHeap.isEmpty()){
const i=numberHeap.extract().data;
frequency[i]++;
const comNode= new ComNode([endTime, i])
timeHeap.insert(comNode);
continue
}else{
frequency[idx]=1;
const comNode= new ComNode([endTime, idx])
timeHeap.insert(comNode);
idx++;
}
}
console.log(Object.keys(frequency).length +"\n"+Object.values(frequency).join(' '))
비교 대상에 대해서 추상화를 적용해서 Node 클래스를 만들고 MinHeap은 Node를 이용해서 우선순위를 정한다. 이렇게 한다면 큐를 하나로 만들고 비교대상에 대해서만 Node를 추가해서 사용할 수 있다.
