프로그래머스 - 호텔 대실

프로그래머스 - 호텔 대실

아이디어

• 사장님 입장에서 최소한의 방의 수를 구하는 것의 관점에서 보면 누가 언제 들어와서 언제 나가는지는 관심이 없다.
• 손님이 온다고 해서 새로 방을 주는 것 보다는 기존 방을 청소해서 사람 새로 받는것이 최소한으로 사용하기 위한 방법
  • 특정 시점에 최대 몇개까지의 방이 필한지만 중요함
  • 최대 방만 준비해두면, 나머지는 청소하고 새로 손님을 받을 수 있음

풀이

1. 누가 언제 들어와서 나가는지는 관심사가 아니니 입실시간, 퇴실시간을 각각 우선순위 큐를 활용하여 저장한다.

2. 가장 빠른 퇴실 시점 전에 입실을 요청하는 예약건이 있다면 현재 배정된 방의 수를 증가시킨다.(기존에 배정한 방이 나가질 않았으니 새로 주는 방법 뿐이 없지 않는가..!)

   2-1. 기존 방을 배정하며 그 시점에 배정한 최대 방의 개수를 갱신한다.
   (최대한 배정한 방이 사실상 최소한으로 준비해야 하는 방의 개수
   -> ex) 가장 빠른 사람의 퇴실 시간 15:20 => 15:20분 전에 예약한 사람들 3명 -> 3명한테 모두 일단 방은 줘야하니 최소한 3개는 줘야함 => 이것이 최소한 방의 수 count 지표가 됨(특정 시점에 최대한 나간 방만큼은 운영해야 모든 예약건을 처리할 수 있음)

3. 가장 빠른 퇴실 시점 전에 예약건이 더이상 없다면, 현재 방 퇴실 처리(현재 방 수 -1)하고 다음 퇴실 시점으로 위 과정을 반복한다.
   

   1. 가장 빠른 방 15:20분 퇴실
      • 14:10 : 기존 방 퇴실하지 않았으니 새로 배정(+1)
      • 14:20 : 기존 방 퇴실하지 않았으니 새로 배정(+1)
      • 15:00 : 기존 방 퇴실하지 않았으니 새로 배정(+1)
      • 16:40 : 15:20분 이후 과정으로 아직 검사하지 않음
      • 15:20 : 기존 방 퇴실 후 청소 완료(-1)
        => 현재 방 : 2개 사용 중, 최대 사용 방 3개

   2. 다음 방 17:00 퇴실
      • 16:40 : 기존 방 퇴실하지 않아 새로 방 배정(+1)
        => 현재 사용 방 : 2개 -> 3개
      • 18:20 : 가장 빠른 퇴실 시점 이후라 아직 검사하지 않음
      • 17:00 : 기존 방 퇴실 후 청소 완료(-1)
        => 현재 사용 방 : 3개 -> 2개

   3. 다음 방 18:20 퇴실
      • 18:20 : 입실 희망
        -> 기존 방 빼고 주면 됨 (현재 사용 방 : 2개 -> 1개 -> 2개)
        -> 이 시점 2개의 방으로 운영됨

   나머지 퇴실 시점 검사하지 않아도됨(입실 예약건이 더이상 없으니)

   특정 시점에 최대로 필요한 방이 이날 예약을 처리할 수 있는 최소한의 방의 개수인 minRoom을 반환한다.

코드

import java.time.Duration;
import java.time.LocalTime;
import java.util.PriorityQueue;

class Solution {
	public int solution(String[][] book_time) {
		int currentRoom = 0;
		int minRoom = 0;

		PriorityQueue<Integer> inTimePQ = new PriorityQueue<>();
		PriorityQueue<Integer> outTimePQ = new PriorityQueue<>();

		// 1. 예약, 체크아웃 손님 시간 큐에 넣기
		for (String[] book : book_time) {
			inTimePQ.offer(transferMinutes(book[0]));
			// 나가는 시간에 + 10분해야(청소 시간) 해당 방을 재사용 할 수 있음
			outTimePQ.offer(transferMinutes(book[1]) + 10);
		}

		// 2. 가장 빠른 퇴실 시점 전에 입실을 요청하는 예약건이 있다면 현재 배정된 방의 수를 증가시킨다.
        // 입실 예약건만 확인
		while (!inTimePQ.isEmpty()) {
			// 가장 빨리 나가는 시점 추출
			int currentOutTime = outTimePQ.poll();
			// 가장 빨리 나갈 사람보다 들어오려는 사람 있을 경우 방 주기
			while (!inTimePQ.isEmpty() && inTimePQ.peek() < currentOutTime) {
				inTimePQ.poll();
				currentRoom++;
				// 최고 빨리 나가는 사람이 나가기 전에 배정한 방의 수 만큼은 최소한 배정해야 모든 예약 처리가 가능하기에 특정 시점에 최대한 배정한 방 개수 저장
				minRoom = Math.max(minRoom, currentRoom);
			}
			// 나갈 시간 전에 들어오는 예약 건들에 대해 방 배정 완료했으니 나갈 시간에 현재 방 나가서 현재 운영중인 방의 수 1개 줄이기
			currentRoom--;
		}
        
		return minRoom;
	}

	/*
		00시부터 몇분이 지난 시간인지 반환하는 메서드
		ex) 01:00 => 60분 지남
	 */
	private Integer transferMinutes(String time) {
		LocalTime time1 = LocalTime.of(0, 0); // "00:00" 형태인 LocalTime객체 생성
		LocalTime time2 = LocalTime.parse(time); // "01:00" 형태를 LocalTime객체
		Duration duration = Duration.between(time1, time2);
		return (int)duration.toMinutes();
	}
}

• 출처 : 프로그래머스 연습문제 풀이 : 호텔 대실 (JAVA)
  • 출처 코드를 조금 수정하였습니다.