BOJ : 1931 회의실 배정 (JS , nodeJS)

소스코드

let fs = require('fs');
const filePath = process.platform === `linux` ? `/dev/stdin` : `예제.txt`; 
let input = fs.readFileSync(filePath).toString().split('\n');
const c = console.log

n = Number(input[0])

let lst = []

for(let i = 1 ; i < n+1 ; i++){
    let numbers = input[i].split(" ").map(Number)
    lst.push(numbers)
}
lst.sort((a, b) => {
        return a[0] - b[0]
    })

lst.sort((a,b) =>{
        return a[1] - b[1]
})

final = 0
let temp = 0 

for(i in lst){
    if (lst[i][0] >= final){
        temp +=1
        final = lst[i][1]
    }
}

c(temp)

 

풀이

처음에는 시작시간 순서대로 포문을 굴려 배열에 count 값을 다 구한 후 최댓값을 뽑아내려 했는데 이렇게 되면 시간 복잡도가 엄청나게 증가하기 때문에 더 좋은 방법을 선택하게 되었다.

 

더 좋은 방법은 일단, 시작 시간에 대해 오름차순으로 정렬을 시켜준다. 그 후 끝나는 시간에 대해 오름차순으로 정렬을 시켜준다. 여기서 '왜 끝나는 시간만 정렬하면 되지 않느냐?'라는 의문점을 가지고 있을 텐데, 만약에 같은 시작 시간과 종료 시간을 가진다면 순서가 엉킬 수 있기 때문에 먼저 시작 시간에 대해 정렬을 해주는 것이다.

 

문제

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정