[백준] 19598번: 최소 회의실 개수 (JavaScript, NodeJS)

문제

서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간은 끝나는 시간보다 항상 작다. N이 너무 커서 괴로워 하는 우리 서준이를 도와주자.

입력

첫째 줄에 배열의 크기 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231−1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최소 회의실 개수를 출력한다.

예제 입력 1 복사

3
0 40
15 30
5 10

예제 출력 1 복사

2

2개 회의실로 3개 회의를 모두 진행할 수 있다. 예를 들어, 첫번째 회의실에서 첫번째 회의를 진행하고 두번째 회의실에서 두번째 회의와 세번째 회의를 진행하면 된다. 1개 회의실로 3개 회의를 진행할 수 없고 3개 이상의 회의실로 3개 회의를 모두 진행할 수 있지만 최소 회의실 개수를 구해야 하기 때문에 2가 정답이 된다.

예제 입력 2 복사

2
10 20
5 10

예제 출력 2 복사

1

정답 풀이

const path = process.platform === "linux" ? "/dev/stdin" : "input.txt"; // 리눅스로 테스트할 땐 따로 설정해주어야 합니다.
const input = require("fs").readFileSync(path).toString().trim().split("\n");

let [n, ...times] = input;
n = +n;
times = times.map(i => { return { start: i.split(' ')[0], end: i.split(' ')[1] } });

// 문제 풀이:
function solution(n, times) {
	let rooms = 0;
	let max = 0;
	const startTimes = times.map(time => { return { time: +time.start, isStart: 1 } });
	const endTimes = times.map(time => { return { time: +time.end, isStart: -1 } });
	const sortedTimes = [...startTimes, ...endTimes].sort((a, b) => a.time === b.time ? a.isStart - b.isStart : a.time - b.time);

	sortedTimes.forEach(time => {
		rooms = time.isStart === 1 ? rooms + 1 : rooms - 1;
		if (max <= rooms) max = rooms;
	});

	return max;
}

// 제출
const answer = solution(n, times);
console.log(answer);

⭐ 문제 핵심 아이디어 ⭐
1. 그리디
2. 어느 시간대에, 최대로 필요한 강의실 수를 파악하는 것.

 

내 풀이를 보면 이해가 잘 안갈수도 있다.

우선 문제가 잘 풀리지 않아서 https://cocoon1787.tistory.com/534 에서 참고했다.

 

처음에는 시작시간을 기준으로 정렬을 한 다음에

기준을 한 배열에서 하나씩 뺀 다음에, 뺀 것과 나머지 배열을 다시 돌면서

뺀 것의 끝시간과 나머지 배열의 시작시간을 비교했다.

이 아이디어는 N의 값이 최대 10만이기 때문에 시간초과가 났다.

 

새로운 아이디어는 시작 시간과 끝 시간을 하나의 배열에 저장을 해놓고,

시작 시간 때는 +1, 끝 시간 때는 -1을 한다. 그럼 어느 특정 시간에서의 회의실 개수가 몇 개 필요한지가 나온다.

 

출처: https://cocoon1787.tistory.com/534

위의 사진을 보게되면

현재 10이라는 시간을 가르키고 있는데, 10 시간에는 최소 4개의 회의실이 필요하다. (3개는 진행중, 하나는 시작)

 

이 아이디어를 가지고 접근을 하면된다.

rooms 변수와 max 변수를 가지고,

시간을 모아둔 배열을 돌면서 isStart가 1이면 시작시간이니까 rooms를 +1 더하고, isStart가 -1이면 끝 시간이니까 rooms를 -1 더한다.

그리고 max 값에는 매번 rooms 변수를 확인하면서 최대를 갱신했을 때만 저장을 한다.

 

요기서 주의할점!

sortedTimes 배열을 만들 때, 만약 start와 end시간이 같다면, 끝 시간이 우선적으로 와야한다.

이유는 만약 [5, 10], [10, 20] 이렇게 있다고 치면,

만약 시작시간이 먼저오게되면, rooms를 +1 더하고 max를 갱신하게 되는데

시간이 같으면 굳이 방을 늘릴 필요가 없기 때문에 끝 시간을 먼저 계산하게 해서 회의를 끝내고, 다음 회의를 시작해야한다.

그리고 최종적으로 max를 리턴하면 정답이 된다.