백준[node.js] > 1931번

문제링크

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

 

문제풀이

이 문제는 정렬 기준을 확립하는게 핵심이다. 최대한의 많은 강의를 듣기 위해서는

1. 강의의 끝나는 시간이 빠른 것 부터 오름차순

2. 강의 끝나는 시간이 같을 때는 강의 시간이 가장늦은 것 부터 내림차순 but 시작하는 시간 = 끝나는 시간 일때는 뒤에 배치 해야한다. 

위 조건대로 배열을 정렬할 시 최대 강의를 진행할 수 있다. 처음에는 확 와닿지 않겠지만 스스로 몇개의 케이스를 만들고 진행하다 보면 왜 위 조건으로 정렬하는지 바로 이해 할 수 있다.

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

let [N, ...arr] = input;

arr = arr.map((str) => {
    return str.split(" ").map((n) => Number(n));
});


arr.sort((prev, next) => {
    // 끝나는 시간이 같을때 
    if (prev[1] === next[1]) {
        
        // 시작시간 = 끝나는 시간이 같을 때는 맨뒤로 빼기 
        if (prev[0] === prev[1]) {
            return 1;
        } else if (next[0] === next[1]) {
            return -1;
        }
        
        // 시작시간이 느릴 수록 앞에 배치
        return next[0] - prev[0];
    }
    
    // 끝나는 시간이 빠를수록 앞으로 배정
    return prev[1] - next[1];
});

answer = 1;

let lectureEndTime = arr[0][1];

for (let i = 1; i < Number(N); ++i) {
    let [startTime, endTime] = arr[i];
    if (lectureEndTime <= startTime) {
        ++answer;
        lectureEndTime = endTime;
    }
}

console.log(answer);