[프로그래머스 Level.2] 호텔 대실 (연습문제) (Java)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/155651

프로그래머스

 

 

 

코딩테스트 연습 > 연습문제 > 호텔 대실

 

 

 

 

문제 설명

 

 

 

호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 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

 

---

입출력 예 설명

 

 

입출력 예 #1

 

위 사진과 같습니다.

 

 

 

입출력 예 #2

 

첫 번째 손님이 10시 10분에 퇴실 후 10분간 청소한 뒤 두 번째 손님이 10시 20분에 입실하여 사용할 수 있으므로 방은 1개만 필요합니다.

 

 

 

 

입출력 예 #3

 

세 손님 모두 동일한 시간대를 예약했기 때문에 3개의 방이 필요합니다.

 

 

 

 

 

 

 

나의 코드

import java.util.*;

class Solution {
    public int solution(String[][] book_time) {
        int answer = 0;
        
        int[][] bookTime = new int[book_time.length][2];
        
        for(int i=0; i<book_time.length; i++) {
            String[] start = book_time[i][0].split(":");
            String[] end = book_time[i][1].split(":");
            
            bookTime[i][0] = Integer.parseInt(start[0]) * 60 + Integer.parseInt(start[1]);
            bookTime[i][1] = Integer.parseInt(end[0]) * 60 + Integer.parseInt(end[1]) + 10;
        }
        
        Arrays.sort(bookTime, (o1, o2) -> o1[0] - o2[0]);
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int idx = 0;
        int time = bookTime[0][0];
        
        while(idx < bookTime.length || !pq.isEmpty()) {
            while(idx < bookTime.length && time >= bookTime[idx][0]) {
                pq.add(bookTime[idx++][1]);
            }
            
            answer = Math.max(answer, pq.size());
            
            if(idx < bookTime.length && pq.peek() > bookTime[idx][0]) {
                time = bookTime[idx][0];
            } else {
                time = pq.poll();
                while(!pq.isEmpty() && time == pq.peek()) pq.poll();
            }
        }
        
        return answer;
    }
}

 

풀이

1. 주어진 book_time을 for문을 돌면서 대실 시작 시각과 대실 종료 시각을 분으로 고쳐 int형 배열에 저장한다.
   대실 종료 후에 10분의 청소 시간이 있으므로 대실 종료 시각에 10분을 더해 저장한다.
2. 시간이 경과함에 따라 예약 시각에 따라 객실을 주기 위해 대실 시작 시각으로 오름차순 정렬한다.
3. 대실 시작 시각이 되면 객실을 주고 대실 종료 시각을 우선순위큐에 담기 위해 Integer를 선언타입으로 하는 우선수위큐를 생성하고(종료시각으로 오름차순 정렬) int형 변수 time을 선언하고 첫번째 예약의 대실 시작 시각으로 초기화하고 예약 처리 수를 인덱스로 체크하기 위한 idx를 0으로 초기화한다.
4. 인덱스가 총 예약 수보다 작거나 우선순위큐가 비어있지 않으면(대실 중인 방이 존재) 반복하는 while문을 생성한다.
5. 내부에 while문을 하나 더 생성하고 예약이 남아있고 현재 시간이 다음 예약의 시작시각과 같거나 크다면 우선순위큐에 해당 예약의 종료시각을 담는 것을 반복한다.
6. 다 담았으면 현재 시간에 객실을 배정한 수인 우선순위큐의 크기와 answer를 비교하여 큰 값을 answer에 저장해가며 최댓값을 저장한다.
7. 그 후에 예약 수가 남아있고 우선수위큐의 첫 데이터가 다음 예약시간보다 크다면 time을 다음 예약의 시작 시각으로 한다. 그게 아니라면 time에 우선순위큐의 첫 데이터인 제일 빠른 종료 시각을 꺼내어 저장하고 하고 만약 우선순위큐에 데이터가 남아있고 같이 종료되는 데이터가 있다면 전부 꺼내도록(대실 종료) 한다.
8. 이렇게 while문을 돌면서 time(현재 시간)이 대실 시작 시각이 되면 종료 시각을 우선순위큐에 담고 우선순위큐는 오름차순으로 정렬되어 있으므로 먼저 종료되는 데이터들이 제일 앞에 있게 된다. 그리고 예약 수만큼 방을 배정했으므로 배정한 객실 수(우선순위큐의 크기)의 최댓값을 answer에 업데이트 하면서 time(현재시간)을 다음 예약 시작시각과 우선수위큐의 첫 객실 종료시각과 비교하여 작은 값으로 변경한다. 객실 종료 시각으로 바꿨다면 종료되는 대실을 우선순위큐에서 꺼내면 된다. 모든 예약을 처리했다면 배정했던 최대 객실 수인 answer를 반환한다.