[알고리즘] 백준 1931 회의실 배정 (javascript)

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

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

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

나의 풀이

const fs = require('fs')
const input = fs.readFileSync('dev/stdin').toString().split('\n')
const totalCount = parseInt(input[0])


let array = [];
  for (let i = 1; i < input.length; i++) {
    const arg = input[i].split(" ").map(Number);
    array.push(arg);
  }

  const sortedArray = array.sort((a, b) => {
    if (a[1] !== b[1]) {
      return a[1] - b[1];
    }
    return a[0] - b[0];
  });

  let count=0;
  let endTime = 0;

  for (let i = 0; i < sortedArray.length; i++) {

      if(sortedArray[i][0]>=endTime){
        endTime = sortedArray[i][1]
          count++

    }
  }
  console.log(count);

풀이 방법

일단 이 문제는 그리디 유형에 속한다.
회의 시작과 끝 시간이 주어지고, 하루동안 최대한 많은 회의를 해야하므로 회의 끝 시간을 기준으로 오름차순 정렬해야한다.
끝 시간이 같다면, 시작 시간을 기준으로 오름차순 정렬해준다.
그 후 endTime과 현재 검사중인 원소의 시작시간을 비교하여 현재의 시작시간이 크거나 같다면 endTime을 현재검사중인 원소의 끝시간으로 재할당 해주고
count를 1회 올린다.

시작시간을 기준으로 정렬한다면...?
나는 처음에 시작시간을 기준으로 정렬해서 풀었다. 하지만 문제에 통과하진 못했다. 그 이유는 시간복잡도 면에서 불리하기 때문이다.
아래에 시작시간을 기준으로 오름차순된 배열이 있다.

[
  [1, 10],
  [2, 3],
  [4, 6],
  [7, 8],
];

위 예시를 풀려면 각 원소를 시작으로 했을 때, 나머지 원소들을 비교해가며 순차적으로 검사하게 된다.
일일히 나열해보면

• 0번 인덱스의 끝 시간을 기준점으로 놓고 1번 비교, 2번 비교, 3번 비교, 총 3회 검사 실시
• 1번 인덱스의 끝 시간을 기준점으로 놓고 2번 비교, 3번 비교, 4번 비교, 총 2회 검사 실시
• ...
• 3번 인덱스 0회
  즉, 3 + 2 + 1 + 0 번 진행

이걸 N개의 배열이라고 가정하면
1 + 2 + ... + N-1 = (N-1)/2 * N = 1/2 * N(N-1) = O(N^2) 의 시간복잡도를 갖는 셈이다.

사실 단순히 생각해보면 이중 for문을 도는것이므로 N^2의 시간복잡도라는것을 잘 알수있다.

하지만 종료시간을 기준으로 다시 정렬해보자.

[
  [2, 3],
  [4, 6],
  [7, 8],
  [1, 10],
];

이 경우엔 끝 시간이 무조건 뒤로갈수록 커지므로 순차적으로 한 번만 비교해서 횟수를 찾으면 된다.
즉 현재 검사하는 원소의 시작시간과 앞 원소의 끝시간만 비교하면 된다는 것이다.

이 경우 배열의 길이가 N이라면 총 N회 실시하게 되므로 O(N)의 시간복잡도를 갖는다.

직관적으로 이해가 가지 않는다면 이렇게 이해해보자
위 배열을 시작시간으로 나열한 경우, 첫 번째 원소는 1, 10 이고, 시작시간의 10보다 큰 시간은 없으므로 사실 이 경우는 검사하는 의미가 없다.
하지만 우리는 N개의 배열을 눈으로 한 번에 검사해낼 수 없으므로, 알고리즘은 매 순간 나머지 원소들을 모두 검사해야 하는 것이다.

반면 끝 시간으로 나열을 한다면, 시작 시간에 비해 가장 빨리 끝나는 회의가 이미 정리되어있기 때문에 가능하다.

예를들어 (2,10), (3,10),(4,10), (5,6), (6,7), (8,9), (9,10) 시작시간으로 정렬된 왼쪽 조합은
이렇게 (5,6), (6,7), (8,9), (2,10), (3,10), (4,10), (9,10) 정렬될것이다.
굳이 검사할 필요 없는 시작시간 2, 3, 4의 원소를 뒤로 밀고, 그 대신 끝 시간이 같은경우엔 시작시간으로 정렬하여 빼먹는 일은 없게 되는 것이다.
(9,10)처럼 말이다.