[Programmers] 호텔 대실 ( PriorityQueue )

 

- 목차

 

문제 설명.

호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 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" 까지로 주어집니다.
    • 예약 시각이 자정을 넘어가는 경우는 없습니다.
    • 시작 시각은 항상 종료 시각보다 빠릅니다.

 

문제 분석.

입장 시간이 빠른 순서대로 손님들이 방문합니다.

새로운 손님이 방문했을 때에 가장 퇴실 시간이 빠른 방의 퇴실 시간과 새로운 입장 시간을 비교해야합니다.

만일 기존 방의 퇴실시간과 새로운 손님의 입장 시간이 겹치게 되면 새로운 방이 필요해지게 되죠.

따라서 입장하는 손님은 입장 시간 순서로 정렬이 필요하고,

예약된 방들은 퇴실 시간을 기준으로 정렬하여 둘을 비교합니다.

 

문제 풀이.

import java.util.*;

class Solution {

  public int solution(String[][] book_time) {
    int answer = 0;
    PriorityQueue<String[]> customers = new PriorityQueue<>(new Comparator<String[]>() {
      @Override
      public int compare(String[] o1, String[] o2) {
        Integer hourA = Integer.parseInt(o1[0].split(":")[0]) * 100;
        Integer minA = Integer.parseInt(o1[0].split(":")[1]);
        Integer hourB = Integer.parseInt(o2[0].split(":")[0]) * 100;
        Integer minB = Integer.parseInt(o2[0].split(":")[1]);
        return hourA + minA - (hourB + minB);
      }
    });

    PriorityQueue<String[]> rooms = new PriorityQueue<>(new Comparator<String[]>() {
      @Override
      public int compare(String[] o1, String[] o2) {
        Integer hourA = Integer.parseInt(o1[1].split(":")[0]) * 100;
        Integer minA = Integer.parseInt(o1[1].split(":")[1]);
        Integer hourB = Integer.parseInt(o2[1].split(":")[0]) * 100;
        Integer minB = Integer.parseInt(o2[1].split(":")[1]);
        return hourA + minA - (hourB + minB);
      }
    });

    for (int i = 0; i < book_time.length; i++) {
      customers.add(new String[]{book_time[i][0], book_time[i][1]});
    }

    while (true) {
      if (customers.isEmpty()) break;
      String[] book = customers.poll();
      // 손님이 없는 경우.
      if (rooms.isEmpty()) rooms.add(book);
      else {
        // 손님이 있는 경우에 방을 체크한다.
        String[] room = rooms.peek();
        int checkOut = getTime(room[1]);
        int newCheckIn = getTime(book[0]);
        if (checkOut + 10 <= newCheckIn) {
          rooms.poll();
          rooms.add(book);
        } else {
          rooms.add(book);
        }
      }
      answer = Math.max(answer, rooms.size());
    }

    return answer;
  }

  int getTime (String o1) {
    Integer hourA = Integer.parseInt(o1.split(":")[0]) * 60;
    Integer minA = Integer.parseInt(o1.split(":")[1]);
    return hourA + minA;
  }
}