[백준] 11000번 강의실 배정 (javascript)

그리디 문제를 풀고있는데 처음으로 어려움을 직면했고 다른 사람들의 풀이를 읽어도 명확하게 이해가 되지 않아서 따로 정리를 했다. 앞으로 문제를 풀고나서 리마인드도 할겸 어려워하는 사람에게 도움도 될겸 겸사겸사 블로그에 정리해볼까 싶다.

 

 

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

11000번: 강의실 배정

문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

출력

강의실의 개수를 출력하라.

예제 입력 1 복사

3
1 3
2 4
3 5

예제 출력 1 복사

2

 

 

---

 

최초 시도 (시간제한으로 실패)

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

function solution(input) {
  let answer = 0;
  const N = Number(input[0]);
  const arr = input.slice(1, N + 1).map((time) => {
    const [startTime, endTime] = time.split(" ").map(Number);
    return {
      startTime,
      endTime,
    };
  });

  const sortedArr = arr.sort((a, b) => {
    // 시작시간이 같은 경우, 종료시간이 더 빠른걸 앞에 배치
    if (a.startTime === b.startTime) {
      return a.endTime - b.endTime;
    }
    return a.startTime - b.startTime;
  });

  let count = 0;
  while (true) {
    let finishHour = -1;
    if (count === N) break;

    for (const meeting of sortedArr) {
      if (meeting.startTime > 0 && meeting.startTime >= finishHour) {
        // console.log(`${meeting.startTime} ~ ${meeting.endTime}`);
        finishHour = meeting.endTime;
        meeting.startTime = -1;
        meeting.endTime = -1;
        count++;
      }
    }
    answer++;
  }

  return answer;
}

console.log(solution(input));

 

강의실별로 startTime, endTime을 묶어서 배열에 저장한 다음에 강의시작시간(startTime) 오름차순으로 정렬하고, 한 강의실에서 최대한 소화할때 까지 처리하고 다시 배열을 처음부터 돌면서 처리했던 강의를 제외하고 나머지 강의들을 또 최대한 소화할 수 있을때 까지 소화하면서 for문이 돈 횟수를 리턴해주는 방식으로 구현했다.

 

유사한 유형의 문제 #1932 풀이를 조금 수정해서 풀었는데 시간제한으로 실패했다. 코드를 짜면서도 뭔가 이렇게 풀면 백빵 틀리겠다라고 생각했었는데 역시나 틀렸다. 

 

뭔가 while문 안에서 for문을 써서 틀렸다고 생각을 했고, 반복문을 한번만 돌게 코드를 수정하면 될 것 같다는 생각이 들었다. 그래서 한번만 돌게 구현하면서 A강의실 쓸지 B강의실 쓸지 아니면 C강의실을 추가할지 고려하는 그런 코드를 짜려고 했는데 이것또한 시간제한에 걸릴 것 같다는 싸한 느낌이 들었다. 분명 뭔가 이렇게 정석(?)대로 가는게 아니라 좀 더 가볍게 코드를 짜야 통과할 것 같다는 확신이 들어서 오랜 고민 끝에 다른 사람들의 풀이를 참고했다.

 

 

다음은 다른 사람들의 풀이를 참고해서 수정한 코드다. 

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "../input.txt")
  .toString()
  .trim()
  .split("\n");

function solution(input) {
  const N = Number(input[0]);
  const classTime = [];

  for (let idx = 1; idx <= N; idx++) {
    const time = input[idx];
    const [startTime, endTime] = time.split(" ").map(Number);
    classTime.push({ time: startTime, isStart: 1 });
    classTime.push({ time: endTime, isStart: -1 });
  }

  const sortedClassTime = classTime.sort((a, b) => {
    if (a.time === b.time) {
      return a.isStart - b.isStart;
    }
    return a.time - b.time;
  });

  let maximumClassCount = 0;
  let currentClassCount = 0;
  for (const classTime of sortedClassTime) {
    if (classTime.isStart === 1) {
      currentClassCount++;
    } else {
      currentClassCount--;
    }
    maximumClassCount = Math.max(currentClassCount, maximumClassCount);
  }

  return maximumClassCount;
}
console.log(solution(input));

 

 

간단히 설명하자면 하나의 강의를 두개로 나눠서 {time: 시작시간, isStart: 1}, {time: 끝시간, isStart: -1} 을 classTime 배열에 넣었다. 예를 들면 "1시 시작, 3시 끝" [{time: 1, isStart: 1}], [{time: 3, isStart:-1}] 로 classTime에 넣었다. 

 

그리고 나서 시작시간 혹은 끝시간이 빠른 순서대로 정렬을 하고 (시작시간 혹은 끝시간이 똑같은 경우 끝시간을 앞에 정렬해줘야함)

 

정렬된 배열(sortedClassTime)을 돌면서 강의가 시작되면 (classTime.isStart === 1) count++, 강의가 끝나면 (classTime.isStart === -1) count--; 해주고,

maximumClassCount 과 currentClassCount 의 값중에 큰 값을 maximumClassCount에 저장하는 방법으로 구현했다. => 최대로 사용된 강의실의 개수를 저장한다.

 

 

ㅠㅠ 인생 쉽지않다.