프로그래머스 - 호텔 대실

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

프로그래머스

 

 

 

 

 

문제

• 최소한의 객실만을 사용하여 예약 손님들을 받음.
• 한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다음 손님들이 사용할 수 있음.
• 필요한 최소 객실의 수 구하기

 

• 1 ≤ book_time의 길이 ≤ 1,000
• book_time[i]는 ["HH:MM", "HH:MM"]의 형태로 이루어진 배열

 

입출력 예시

• 입력 : book_time [["15:00", "17:00"], ["16:40", "18:20"], ["14:20", "15:20"], ["14:10", "19:20"], ["18:20", "21:20"]]
• 출력 : 3

 

출처 : 프로그래머스 (https://school.programmers.co.kr/learn/courses/30/lessons/155651)

 

 

 

 

 

풀이

그리디한 방법으로 풀어야 하는 문제이다. 시작 시간이 빠른 것부터 차례로 방에 넣어야 한다.

저렇게 시작 시간과 끝나는 시간이 주어지고 최댓값이나 최솟값을 구하는 문제 유형으로 회의실 문제가 유명하다.

 

백준 - 회의실 배정 (https://www.acmicpc.net/problem/1931)

프로그래머스 - 요격 시스템 (https://school.programmers.co.kr/learn/courses/30/lessons/181188)

 

 

 

'호텔 대실' 문제도 회의실 문제와 풀이가 비슷하나 더 생각해야 될 부분이 있었다.

 

• String("HH:MM") 형태의 값을 분 단위(int)로 바꾸기
  • timeToInt 함수 :  ":"를 기준으로 시간과 분을 나누고, 분으로 연산해 리턴

 

• 시작 시간을 기준으로 오름차순 정렬하기
  
  • 예약을 시작 시간에 맞춰 차례대로 방에 배정할 것이다. 

 

• 최소힙(우선순위 큐) 사용
  • 최소의 방을 쓰려면, 새로운 예약 시간을 방에 배정할 때 예약이 빨리 끝나는 방을 찾아 비교를 해야 한다. 큐에 대실 중인 예약들을 넣고, 최소힙으로 정렬을 해 front에 빨리 끝나는 시간이 나오도록 한다.
  • 예약이 빨리 끝나는 방의 종료 시간 + 10(청소시간)을 기준으로 새로운 예약 시간이
    • 뒤에 있다면, 새로 방을 배정할 필요가 없다. (이전의 예약을 대실 중인 큐에서 제거해준다.)
    • 앞에 있다면, 시간이 겹치므로 새로 방을 배정해야 한다. (정답 카운트를 늘린다)
    • 대실 중인 큐에 넣는다.

 

 

출처 : 나

 

 

 

 

 

코드

import java.util.*;

class Solution {
    public int solution(String[][] book_time) {
        //분단위로 바꾸기
        int[][] times = new int[book_time.length][2];
        
        for(int i = 0; i < book_time.length; i++) {
            for(int j = 0; j < 2; j++) {
                times[i][j] = timeToInt(book_time[i][j]); 
            }
        }
        
        //시작 시간 기준으로 오름차순 정렬
        Arrays.sort(times, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]); 
        
        //끝나는 시간 + 10(청소시간) > 다음 시작 시간 -> 새로운 방
        int answer = 1;
        PriorityQueue<Integer> queue = new PriorityQueue<>(); //대실 중
        queue.add(times[0][1]);
        
        for(int i = 1; i < times.length; i++) {
            if(queue.peek() + 10 > times[i][0]) {
                answer++;
            } else {
                queue.remove();
            }
            queue.add(times[i][1]);
        }
        
        return answer;
    }
    
    public int timeToInt(String time) {
        String[] str = time.split(":");
        return 60 * Integer.parseInt(str[0]) + Integer.parseInt(str[1]);
    }
}

 

 

 

 

 

결과

 

 

 

 

 

배운점

• 최소 힙(우선순위 큐) 사용