[프로그래머스] 호텔 대실 (LV2)

🔗 문제 링크

코딩테스트 연습 - 호텔 대실

---

⏳ 풀이

1. 대실 시작 시간을 기준으로 오름차순 정렬하여 배열에 담아준다.

2. 우선순위 큐에 배열 순서대로 아래 조건을 고려하며 대실이 끝나는 시간을 하나씩 넣어준다.

   • 우선순위 큐의 peek값 (대실 종료가 가장빠른 예약)과 다음 대실의 시작시간과 비교
   • 다음 대실 시작시간 > pq.peek()+10 을 만족하면 peek 값을 다음 대실의 끝나는 시간으로 갱신
   • 다음 대실 시작시간 > pq.peek()+10 을 만족하지 못한다면 pq에 다음 대실의 끝나는 시간을 삽입

3. 우선순위 큐의 사이즈를 반환해준다.

---

💡 고찰

해당 문제 풀이에 핵심은 우선순위 큐에 값을 넣는 것 == 새로운 객실을 생성!

최초의 우선순위 큐에 시작 시간이 가장 빠른 대실예약의 종료 시간을 넣어준다. 이것은 객실 1개를 새롭게 생성한다고 생각하면 된다.

우선순위 큐를 사용하기 때문에 항상 퇴실 시간이 가장 빠른 예약이 최상단의 위치하게 된다. 다음 예약시간과 현재 퇴실이 가장 빠른 객실만 비교하고 예약이 가능하면 최상단에 위치한 객실의 종료시간을 갱신해주고 만약 불가능 하다면 우선순위 큐에 다음 예약 종료시간을 넣어주면 된다. ( 객실 1개 추가 )

마지막으로 큐의 사이즈(총 생성된 객실)를 반환해주면 끝!

비슷한 유형의 문제가 종종 보이는데 한번 풀때 확실히 풀어두면 다음에 고민할 필요가 없는 것 같다. 그래도 주의 할점은 유형이 비슷해도 조금씩 다른 부분들이 존재할 수 있으니 자만하지 말고 요구사항을 꼼꼼히 살펴보자!

💻 소스코드

import java.io.*;
import java.util.*;

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

        Node[] arr = new Node[book_time.length];
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int i = 0; i < book_time.length; i++) {

            String st[] = book_time[i][0].split(":");
            String ed[] = book_time[i][1].split(":");

            int start = (Integer.parseInt(st[0]) * 60) + Integer.parseInt(st[1]);
            int end = (Integer.parseInt(ed[0]) * 60) + Integer.parseInt(ed[1]);

            arr[i] = new Node(start, end);
        }

        Arrays.sort(arr);

        for (int i = 0; i < arr.length; i++) {
            if (pq.isEmpty()) pq.offer(arr[i].end);
            else {
                if (arr[i].start >= pq.peek() + 10) {
                    pq.poll();
                    pq.offer(arr[i].end);
                } else {
                    pq.offer(arr[i].end);
                }
            }
        }

        answer = pq.size();
        return answer;
    }

    static class Node implements Comparable<Node> {

        int start, end;
        Node(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(Node o) {
            if (this.start == o.start) {
                return this.end - o.end;
            } else return this.start - o.start;
        }
    }
}

public class pg_호텔대실 {

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