백준 문제 풀이 : 회의실 배정 (1931)

내 문제 풀이 방법

정렬과 그리디를 사용하면 되겠다는 감이 왔지만, 코드로 구현하는 데 애를 먹음;;

우선 정렬 방법 자체가 어려웠다. 문제를 풀 수 있도록 정렬하려면 회의실의 시작시간과 끝시간을 오름차순으로 정렬해야한다.

조건은 아래와 같다.

1. 종료 시간 기준으로 오름차순 정렬
2. 종료 시간이 같은 두 회의 중, 시작 시간이 더 빠른 회의를 선택해야 최대로 회의실을 배정하기 때문에 시작 시간도 오름차순으로 정렬

조건은 알겠는데, 이를 코드로 구현하는 게 어려웠다...

이후에는 종료 시간을 추출한 뒤, 다음 회의실의 시작 시간이 종료 시간보다 크면 개수를 카운트하면 된다.

 

풀이

/**
 * 졍렬과 그리디로 푼다.
 * 1. 정렬 : 최대개수를 출력하기 위해
 * 2. 반복문 통해 비교
 */

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

let [n, ...arr] = input;
let data = arr.map((item)=>{return item.split(' ').map(Number)})

// 정렬
data.sort((a,b)=> { return a[1]===b[1] ? a[0]-b[0] : a[1]-b[1]});

let count = 0;
let endTime = 0;
// 가능한 경우를 다 해본다. 그리디
data.forEach((item)=>{
    if( item[0] >= endTime ){
        endTime = item[1];
        count += 1;
    }
});

console.log( count );

 

TIL

sort() 메소드를 아래와 같이 작성하는 게 중요하다. 

왜? 끝시간이 같으면 시작시간이 빠른게 먼저 오도록 정렬하기 위해서! ⭐️

arr.sort((a, b) => (a[1] === b[1] ? a[0] - b[0] : a[1] - b[1]));

 

링크

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