(알고리즘 스터디) (Programmers) 호텔 대실 🏨

🌟 프로그래머스 /  Level2 / 호텔 대실

📃 문제

프로그래머스

🚫 제한 사항

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

👀 입출력 예

🤔 풀이 방법

1️⃣ 아이디어

➡️ 대실 시작 시간을 기준으로 예약 건들을 정렬한 후 예약을 하나씩 확인하며 비워진 룸이 있으면 들어가고 없으면 룸을 추가하여 들어가는 과정을 반복한다.

 

2️⃣ 필요한 자료구조

① Room Class

➡️ 예약 건들의 시작 시간과 종료 시간을 정리할 Room Class 를 생성하였다. 이때 시간&분으로 굳이 나누지 않고 분형태로 변환하여 저장하였고, 대실 종료 후 10분의 정리시간이 있는 점을 고려하여 종료 시간 자체에 10분을 더하였다. 또한 추후 우선순위 큐에 담을 때 정렬 기준을 제공하기 위해 시작시간을 기준으로하는 Comparable 인터페이스를 구현하였다.

// Room 클래스 선언
class Room implements Comparable<Room> {
    int startTime;
    int endTime;
    
    public Room (int sh, int sm, int eh, int em) {
        this.startTime = sh*60 + sm;
        this.endTime = eh*60 + em + 10; // 먼저 청소시간 10분을 더한다.
    }
    
    @Override
    public int compareTo (Room other) {
        return Integer.compare(this.startTime, other.startTime);
    }
}

② Priority Queue (우선 순위 큐)

➡️ Room 클래스를 담는 우선 순위 큐를 생성하였다.

// 우선 순위 큐 생성
Queue<Room> pq = new PriorityQueue<>();

③ ArrayList (리스트)

➡️ 룸의 개수를 확인하기 위한 배열을 생성하였다.

// 리스트 선언
ArrayList<Room> roomList = new ArrayList<>();

💻 풀이 코드

import java.util.Queue;
import java.util.PriorityQueue;
import java.util.ArrayList;

// Room 클래스 선언
class Room implements Comparable<Room> {
    int startTime;
    int endTime;
    
    public Room (int sh, int sm, int eh, int em) {
        this.startTime = sh*60 + sm;
        this.endTime = eh*60 + em + 10; // 먼저 청소시간 10분을 더한다.
    }
    
    @Override
    public int compareTo (Room other) {
        return Integer.compare(this.startTime, other.startTime);
    }
}
class Solution {
    public static ArrayList<Room> roomList;
    
    public int solution(String[][] book_time) {
        int answer = 0;
        int roomCnt = 0;

        // 입력값 정리
        String[] start, end;
        Queue<Room> pq = new PriorityQueue<>();
        
        for (String[] times : book_time) {
            start = times[0].split(":");
            end = times[1].split(":");
            
            pq.add(new Room(Integer.parseInt(start[0]), Integer.parseInt(start[1]), 
                            Integer.parseInt(end[0]), Integer.parseInt(end[1])));
        }
        
        // Queue 들을 담을 ArrayList 선언 & 초기값 처리
        roomList = new ArrayList<>();
        
        roomList.add(pq.poll());
        
        System.out.println(roomList.size());
        
        // Queue 처리
        while(!pq.isEmpty()) {
            Room room = pq.poll();
            int[] roomInfo = minEndTime();
            
            // 경우 (1) : 새로운 방의 시작 시간이 나머지 방들의 종료시간 보다 늦은 경우
            if (room.startTime < roomInfo[0]) {
                // 방을 추가하여 넣음
                roomList.add(room);
                // System.out.println(roomList.size());
            }
            // 경우 (2) : 새로운 방의 시작 시간이 나머지 방들이 종료시간 보다 빠른 경우
            else {
                // 최소 종료 시간 방에 해당 방을 넣는다.
                roomList.set(roomInfo[1], room);
            }
        }
        
        // 총 원소의 개수 = 필요한 방의 개수
        return roomList.size();
    }
    public int[] minEndTime () {
        int[] info = {Integer.MAX_VALUE, 0};
        
        for (int i=0; i<roomList.size(); i++) {
            if (roomList.get(i).endTime < info[0]) {
                info[0] = roomList.get(i).endTime;
                info[1] = i;            
            }
        }
        
        return info;
    }
}

🧐 추가공부