백준 JS 1931번 회의실 배정. 그리디

첫번째 시도

시작시간을 기준으로 정렬을 한 다음, 늦은시간, 즉 뒤에서 부터 순회를 돌면서, 각각의 시간 뒤에 올 수 있는 시간표의 갯수를 나타내는 arr 배열을 만듦.

const Data = `4
0 1
1 5
2 3
4 5`
  .trim()
  .split("\n").map(v => v.split(" ").map(Number));
  
  const arr = Array(...Data.shift()).fill(1)
Data.sort((a, b) => a[0] - b[0]);

for (let i = arr.length - 1; i >= 0; i--) {
  for (let j = i+1; j < arr.length; j++) {
    if (Data[i][1] <= Data[j][0] &&
      arr[i] < arr[j] + 1) {
        arr[i] = arr[j] + 1
    }
  }
}

console.log(arr);

결과

시간 복잡도 O^2의 풀이로. 주어진 Data의 길이는 10만. 최대 순회 길이는 10만*10만으로 시간초과라는 결과가 나옴.

---

두번째 시도

1. 끝 시간을 기준으로 정렬을 한다. 그러면 뒤에오는 시작시간의 끝 시간보다 클 경우 자동적으로 최적해를 갖추게 된다(그리디)

const fs = require('fs')
const Data = fs.readFileSync('/dev/stdin').toString().trim()
  .split("\n")
  .map((v) => v.split(" ").map(Number));

Data.shift();

Data.sort((a, b) => a[1] - b[1]);

const answer = [Data[0]];
for (let i = 1; i < Data.length; i++) {
  if (Data[i][0] >= answer[answer.length - 1][1]) {
    answer.push(Data[i]);
  }
}
console.log(answer.length)

결과

틀렸습니다.

반례

4

3 3

2 3

1 3

2 2 

---

세번째 시도

1.위 반례를 통과하기 위해 정렬을 수정해 준다.

const fs = require('fs')
const Data = fs.readFileSync('/dev/stdin').toString().trim()
  .split("\n")
  .map((v) => v.split(" ").map(Number));

Data.shift();

Data.sort((a, b) => a[0] - b[0]).sort((a, b) => a[1] - b[1]);

const answer = [Data[0]];
for (let i = 1; i < Data.length; i++) {
  if (Data[i][0] >= answer[answer.length - 1][1]) {
    answer.push(Data[i]);
  }
}
console.log(answer.length)

결과

정답입니다.

---

그리디 개념을 통해서 시간복잡도를 줄일 수 있다는 개념을 조금 더 이해할 수 있었던 문제였다.