프로그래머스 연습문제 풀이 : 호텔 대실 (JAVA)

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/155651?language=java 

프로그래머스

❓  문 제

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

💻  입 출 력  예

❗️ 입 출 력  예  설 명

입출력 예 #1

위 사진과 같습니다.

 

입출력 예 #2

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

 

입출력 예 #3

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

---

💡 문 제  풀 이

가장 적은 수의 방을 사용해야 하기 때문에 탐욕법(Greedy) 기법을 사용하면 될 것 같다.

 

문제를 살펴보면 아래와 같다.

• 가장 먼저 들어오는 사람이 을 기준으로 방 1개이다.
• 사람이 방을 사용하고 있으면 방을 하나더 늘린다.
• 퇴실하고 10분은 청소시간이 있기 때문에 사용할 수 없다.

위의 3개의 요건을 지키면 되는 문제이다.

 

그럼 인자 값중에 가장 먼저 들어오는 사람에 대한 기준을 잡아야한다.

입장 시간을 분으로 변환하여 00:00 분을 기준으로 누가 가장 먼저 들어오고 나가는지를 파악할 수 있다.

 

예를들어 01:00 입장인 사람 A와 02:00 입장인 사람 B의 시간을 분으로 변환하면 60과 120이다.

 

해당 두수를 우선순위 큐에 [낮은 수가 우선순위가 더 높다고 판단] 넣게 되면 60, 120으로 정렬이 되며 peek을 사용해 최 상위 숫자를 꺼내게 되면 가장 먼저 들어오는 사람의 시간이 될 것이다.

 

PriorityQueue<Integer> in = new PriorityQueue<>();
PriorityQueue<Integer> out = new PriorityQueue<>();

따라서 들어오는 시간과 나가는 시간을 넣어줄 우선순위 큐 2개를 선언한다.

 

// 들어오는 예약 현황 하나씩 받기
for(String[] b : book_time){
    in.offer(calcMin(b[0]));

    // 퇴실 이후 청소 10분이 있기 때문에
    // 다음 사람이 쓰기 위해서는 10분 뒤부터 입실 가능
    out.offer(calcMin(b[1]) + 10);
}

예약 현황을 하나씩 열어 들어오는 시간과 퇴실 시간을 각각 우선순위 큐에 넣어준다. 

여기서 퇴실 이후 10분 동안은 청소시간이기 때문에 +10 한 값을 큐에 넣어준다.

 

# calcMin 함수는 입력된 18:00 등의 값을 오로지 분으로 변환해주는 함수이다.

 

while(!out.isEmpty() && !in.isEmpty()){

    // out 이 있는 경우는 한명이 들어온 경우
    int o_p = out.poll();

    // 사람이 나갔다는 가정 하에 cnt --
    cnt--;

    // 들어올 사람이 추가적으로 있으며
    // 나갈 사람보다 더 일찍 들어올 예정이면
    // cnt 를 하나 증가시켜 줘야 한다.
    while(!in.isEmpty() && in.peek() < o_p){
        in.poll();
        cnt++;
    }
    answer = Math.max(answer, cnt);
}

이번 문제의 핵심 알고리즘 부분이다.

 

들어오는 사람 기준이 아닌 나간 사람 기준으로 반복문을 돌린 이유는

 

out.poll을 하게 되면 예약자 중 가장 빨리 나간 시점이 나오게 되며 해당 시점보다 입장 시간이 빠른 사람들의 명수가 자연적으로 필요한 방의 갯수가 되게 된다. 

 

퇴실시간 중 제일 빠른 시간이 15:20 분이기 때문에 입실시간이 14:10, 14:20, 15:00 중 어느 누가 퇴실시간이 15:20 분인지 상관없이 최소 방이 3개가 필요하게 된다.

 

이런식으로 퇴실시간을 기준으로 입실해야하는 명수를 구한다음 max 값을 계속해서 갱신해 나가면 필요한 방의 최대 갯수를 구할 수 있다.

 

⌨️ 풀 이  코 드

import java.util.PriorityQueue;

public class 호텔대실 {
    public static void main(String[] args) {
        Solution_호텔대실 s = new Solution_호텔대실();
        String[][] book = {
                {"15:00", "17:00"}, {"16:40", "18:20"}, {"14:20", "15:20"}, {"14:10", "19:20"}, {"18:20", "21:20"}
        };

        String[][] b = {
                {"15:00", "17:00"}
        };

        System.out.println(s.solution(book)); // 3
    }
}

class Solution_호텔대실 {
    public int solution(String[][] book_time) {
        int answer = 0;

        PriorityQueue<Integer> in = new PriorityQueue<>();
        PriorityQueue<Integer> out = new PriorityQueue<>();

        // 예약 손님은 무조건 한명 이상
        int cnt = 1;

        // 들어오는 예약 현황 하나씩 받기
        for(String[] b : book_time){
            in.offer(calcMin(b[0]));

            // 퇴실 이후 청소 10분이 있기 때문에
            // 다음 사람이 쓰기 위해서는 10분 뒤부터 입실 가능
            out.offer(calcMin(b[1]) + 10);
        }

        System.out.println(in);
        System.out.println(out);

        // 들어온 사람과 나갈 사람이 들어있는 큐가 빌때까지 반복
        while(!out.isEmpty() && !in.isEmpty()){

            // out 이 있는 경우는 한명이 들어온 경우
            int o_p = out.poll();

            // 사람이 나갔다는 가정 하에 cnt --
            cnt--;

            // 들어올 사람이 추가적으로 있으며
            // 나갈 사람보다 더 일찍 들어올 예정이면
            // cnt 를 하나 증가시켜 줘야 한다.
            while(!in.isEmpty() && in.peek() < o_p){
                in.poll();
                cnt++;
            }
            System.out.println("");
            System.out.println("===TEST===");
            System.out.println(in);
            System.out.println(out);
            System.out.println("cnt = " + cnt);
            System.out.println("answer = " + answer);
            answer = Math.max(answer, cnt);
        }

        return answer;
    }

    public int calcMin(String s){
        int min = 0;

        String[] time = s.split(":");

        // 시 -> 분
        min += Integer.parseInt(time[0]) * 60;

        // 분
        min += Integer.parseInt(time[1]);

        return min;
    }
}

 

✅ 비 고

우선순의 큐의 이론과 그리디를 적절하게 섞어 사용하면 해결할 수 있는 문제이다.

 

우선순의 큐의 사용 시간이 배열에 해당 값들을 저장하고 sort 하는 것보다 빠른 것 같아 큐를 사용할 수 있다면 사용하는 편이 좋다.