🔴 문제
🟡 Sol
const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const inputs = fs.readFileSync(path).toString().trim().split('\n');
const n = Number(inputs.shift());
const timetable = inputs
.map((it) => it.split(' ').map(Number))
.sort((a, b) => a[1] - b[1] || a[0] - b[0]);
let currentIdx = 0;
let [start, end] = timetable[currentIdx];
let currentCnt = 1;
for (let i = currentIdx + 1; i < n; i++) {
const [nextStart, nextEnd] = timetable[i];
if (end <= nextStart) {
currentCnt += 1;
[start, end] = timetable[i];
}
}
console.log(currentCnt);
🟢 풀이
⏰ 소요한 시간 : -
그리디 문제 유형.. 역시 풀이를 봤다.
입력 시간들을 끝나는 시간이 짧은 순서대로 정렬을 한다. 그래야 다음에 더 많은 경우의 수에서 선택이 가능하다.
예를들어 시작 시간이 0, 끝나는 시간이 2인 경우와 시작 시간이 0, 끝나는 시간이 6인 경우가 있다고 하자.
끝나는 시간이 2인 경우가 먼저 오도록 정렬해야지만 이 경우의 수를 먼저 선택하고 그 다음 선택 과정에서 3부터 시작하는 회의를 선택할 수 있기 때문에 선택지가 더 많아진다.
근데 만약 끝나는 시간이 동일한 경우는 a[1] - b[1]이 0이 될텐데 이 경우에는 || 연산자를 사용에 회의 시작시간이 짧은시간을 먼저 선택할 수 있도록 해준다.
왜냐하면 2 2 같이 시작시간과 끝 시간이 같은 경우는 2 2 가 뒤에와야 1 2 를 회의를 진행하고, 2 2 도 회의를 진행할 수 있기 때문이다.
정렬을 마친 후에는 첫 회의를 기준으로 회의가 끝나는 시간과 다음 회의의 시작 시간을 비교해서 회의 일정을 조절해주면 된다.
2
1 2
2 2자세한 풀이는 아래 링크를 참고해 보면 좋을 것 같다.
그래서 이 해가 정답인지 수학적으로 어떻게 증명해서 그리디를 풀이하느냐? 하면...
증명식을 세우기는 매우 어려우니.. 계속 연습해서 내 풀이에 확신을 가지게 되는 것이 방법이라고 한다.
🔵 Ref
록타르오가르