호텔 대실 (그리디 알고리즘)

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

프로그래머스

 

 

 

문제 풀이

 그리디 알고리즘의 대표적인 예시인 회의실 문제를 약간 변형한 문제이다. 우선순위 큐(Priority Queue, 최소 힙)를 사용하는 그리디(Greedy) 알고리즘을 사용하는 것이 가장 정석적인 풀이이다.

 

핵심은 가장 빨리 비는 방에 가장 급한 예약 시간 순으로 들어가야 한다는 것!

 

전체 알고리즘

1. 모든 예약 시간을 시작 시간으로 정렬한다. (가장 급한 예약 시간 순으로 들어가야 하기 때문에)

2. 객실이 다시 사용 가능한 시간을 넣어줄 우선순위 큐를 생성한다. (객실이 다시 사용 가능한 시간 = 예약 종료 시간 + 청소 시간)

3. 예약을 순회하면서 사용 가능한 방이 있다면 그 방을 지운다. (방이 재사용 됐기 때문에)

4. 우선 순위 큐에 새 예약의 사용 가능한 시간을 넣는다.

5. 마지막에 큐의 size를 리턴한다.

 

 

작성한 코드 (정답)

import java.util.*;

class Solution {

    public int solution(String[][] book_time) {

        Arrays.sort(book_time, new Comparator<String[]>() {
            @Override
            public int compare(String[] o1, String[] o2) {
                return o1[0].compareTo(o2[0]);
            }
        });

        //우선 순위 큐 (방 별 예약 종료 시간)
        PriorityQueue<Integer> que = new PriorityQueue<>();

        for (String[] book : book_time) {

            int start = toTotalMinute(book[0]);
            int end = toTotalMinute(book[1]) + 10;

            if (!que.isEmpty() && que.peek() <= start) {
                que.poll();
            }

            que.offer(end);
        }

        return que.size();
    }

    // 시간:분을 분 총합으로 변환
    private int toTotalMinute(String time) {
        String[] split = time.split(":");
        return Integer.parseInt(split[0]) * 60
                + Integer.parseInt(split[1]);
    }
}

 

 

마무리

PriorityQueue<Integer> que = new PriorityQueue<>();

 

사실 위와 같이 자바에서 기본으로 제공하는 우선순위 큐가 있는지 모르고, 큐를 순회하면서 사용 가능한 방을 찾도록 구현했었다. 하지만 위와 같이 Integer로 큐를 만들면 poll()을 할 때 가장 낮은 숫자부터 반환하기 때문에 순회할 필요가 없어진다.

 

우선순위 큐에 대해서는 블로그에 다시 정리할 예정이다.