백준 JS 11000번 강의실 배정 그리디

 

11000번: 강의실 배정

첫 번째 시도

map객체를 이용하여, 시작 시간이 빠른 강의부터 선택한 다음, 선택된 강의가 끝나는 시간과 시작시간이 같은 객체를 골라서 하나로 묶으면서 필요한 강의실의 개수를 찾는 알고리즘을 만들었다.

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n")
const N = +input.shift()
const data = input.map(v => v.split(" ").map(Number)).sort((a,b)=>a[0]-b[0])
const mapObj = new Map();
for(let [str,end] of data){
  if(mapObj.has(str)){
    mapObj.set(str, [...mapObj.get(str),end])
  }else{
    mapObj.set(str,[end])
  }
}

let count = 0;
while([...mapObj.keys()].length !== 0){
  const key = [...mapObj.keys()][0]
  next(key)
  count++
}
console.log(count)
function next (key) {
  const value = [...mapObj.values()][0][mapObj.get(key).length-1]
  mapObj.get(key).pop()
  if(mapObj.get(key).length === 0){
    mapObj.delete(key)
  }
  if(!mapObj.has(value)){
    return
  }
  if(mapObj.get(value).length === 0){
    mapObj.delete(value)
    return
  }
  mapObj.get(value).pop()
  return next(value)
}

문제

1. 시작 시간의 순서를 기억하기 위해 객체가 아닌 Map객체를 이용하였는데, 가독성이 좀 떨어지는 느낌.
2. 반례는 다 맞았지만, 메모리 초과 문제가 나타남.

---

두 번째 풀이

좀 더 쉬운 방법이 있었다.

필요한 강의실의 수는 중첩된 강의가 가장 많은 시간의 강의의 수가 정답.

따라서 시간을 기준으로 순회를 하면서, 강의가 가장 많이 겹치는 max값을 찾으면 된다.

let fs = require('fs');
let [N, ...input] = fs.readFileSync('/dev/stdin').toString().trim().split("\\n")
const data = input.map(v => v.split(" ").map(Number))
const objArr = [];
for(let [str,end] of data){
  objArr.push({time:str, start:true})
  objArr.push({time:end, start:false})
}
objArr.sort((a,b)=>a.time===b.time ? a.start-b.start :a.time-b.time)
 //time이 같다면, false가 앞에 와야함. 강의가 끝나고 다른 강의가 시작 되어야함.
 //강의가 먼저 시작되면 정답에 +1값이 생길 수 있음.
let max = 0;
let cur = 0;
for(let {start} of objArr){
  start ? cur++ : cur--
  max = max < cur ? cur : max
}
console.log(max)

---

일단 다른사람의 코드를 보면서 깔끔하게 코드 쓰는 법을 좀 더 익혀야겠다는 생각이 든다.

그리디 문제를 풀다보니 정점을 잇는 문제보다 시간을 기준으로 순회하는 문제가 자주 보이는 것 같다!