[programmers] 호텔 대실

📝 [Lv2] 호텔 대실

👀 문제 설명

호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다음 손님들이 사용할 수 있습니다.
예약 시각이 문자열 형태로 담긴 2차원 배열 book_time이 매개변수로 주어질 때, 코니에게 필요한 최소 객실의 수를 return 하는 solution 함수를 완성해주세요.

 

🚨 제한 사항

• 1 ≤ book_time의 길이 ≤ 1,000
  • book_time[i]는 ["HH:MM", "HH:MM"]의 형태로 이루어진 배열입니다
    • [대실 시작 시각, 대실 종료 시각] 형태입니다.
  • 시각은 HH:MM 형태로 24시간 표기법을 따르며, "00:00" 부터 "23:59" 까지로 주어집니다.
    • 예약 시각이 자정을 넘어가는 경우는 없습니다.
    • 시작 시각은 항상 종료 시각보다 빠릅니다.

 

💻 입출력 예

book_time	result
[["15:00", "17:00"], ["16:40", "18:20"], ["14:20", "15:20"], ["14:10", "19:20"], ["18:20", "21:20"]]	3
[["09:10", "10:10"], ["10:20", "12:20"]]	1
[["10:20", "12:30"], ["10:20", "12:30"], ["10:20", "12:30"]]	3

 

✨ 풀이 설명

기본적인 강의실 배정 문제이다. 우선순위 큐를 이용하면 시간 측면에서 더 빨리 풀 수 있겠지만 배열의 길이가 길지 않으니, 우선순위큐를 구현하지 않고 매 타임마다 정렬을 해주었다.

우선, 시간 순서대로 정렬하기 위해 데이터를 조작해 주었다. 분 기준의 Number 형식으로 바꾼 후, 시작 시간을 기준으로 오름차순 정렬을 해주었다.

처음 호텔 객실은 한 개가 필요하므로 rooms에 맨 처음 시간을 넣어주었다. 넣는 시간은 다음 타임의 시작 시간과 비교하기 편하게 종료 시간으로 넣어주었다.
남은 시간들을 비교하며 종료 시간 + 청소 시간보다 이른 시간일 경우에는 새로운 객실을 추가해 주는 의미로 rooms에 push 했고, 해당 객실에 가능할 경우에는 해당 객실을 뺀 후, 다음 시각을 넣어주었다. (같은 객실에 다음 사람이 들어간다는 개념으로 !)
rooms를 매번 정렬해 준 이유는, 가장 빨리 종료되는 시간과 비교하는 것이 제일 효율적이기 때문이다. 

rooms의 크기를 구해주면 총 사용한 객실 수를 알 수 있다.

 

🕵️‍♂️ 코드

function solution(book_time) {

  const bookTime = book_time.map(times =>

    times.map(time => {

      const [hh, mm] = time.split(':');

      return hh * 60 + +mm;

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

  const rooms = [];

  rooms.push(bookTime[0][1]);

  for (let k = 1; k < bookTime.length; k++) {

    if (rooms[0] + 10 > bookTime[k][0]) rooms.push(bookTime[k][1]);

    else {

      rooms.shift();

      rooms.push(bookTime[k][1]);

    }

    rooms.sort((a, b) => a - b);

  }

  return rooms.length;

}