[프로그래머스] 호텔 대실 자바 (Level 2)

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

1. 문제 요약

• 주어진 예약을 모두 소화하는데 필요한 방 갯수의 최소값 구하기
• 퇴실시간의 10분 후부터 다음 입실 가능.

2. 핵심 아이디어

• 모든 예약을 입실시간 기준 정렬
• 최소 힙(우선순위 큐)을 사용하여 각 방의 다음 사용 가능 시간을 추적
• 예약마다 사용 가능한 방이 있는지 확인
  • 가능: 해당 방 재사용 (방의 다음 사용 가능 시간 갱신)
  • 불가능: 새로운 방 추가

3. 풀이 코드

public int solution(String[][] book_time) {
        //1. 시작시간 기준으로 예약시간 정렬
        Arrays.sort(book_time, (a, b) -> toMinutes(a[0]) - toMinutes(b[0]));

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

        for(String[] time : book_time){
            int st = toMinutes(time[0]);
            int et = toMinutes(time[1]) + 10;

            //입실가능한 방이 있다면 재사용
            if(!rooms.isEmpty() && rooms.peek() <= st){
                rooms.poll();
            }

            //예약종료시간 입력
            rooms.add(et);
        }

        return rooms.size();
    }

    private int toMinutes(String time) {
        String[] parts = time.split(":");
        return Integer.parseInt(parts[0]) * 60 + Integer.parseInt(parts[1]);
    }

4. 회고 및 느낀점

• PriorityQueue와 일반 Queue의 차이점항목 Queue PriorityQueue

  기본 자료구조	FIFO (선입선출)	우선순위 기반으로 정렬됨
  사용 예시	LinkedList, ArrayDeque	PriorityQueue<Integer> 등
  추출 순서	가장 먼저 추가된 요소	우선순위가 가장 높은 요소
  정렬 기준	없음	Comparable 구현 또는 Comparator 제공
  null 허용 여부	구현체에 따라 다름	null 요소 허용 안 함

• PriorityQueue의 poll()은 내부적으로 자동 정렬되어 있어서 가장 낮은 숫자(혹은 높은 우선순위)가 먼저 나옴
• 큐방식으로 했을 때 보다 훨씬 효율적이고 직관적일 수 있구나 라는걸 느낌.

상황 추천 구조

단순 순차 처리	Queue
가장 빠른 작업 / 최소값 / 최대값 우선 처리	PriorityQueue
BFS 탐색 (일반 큐)	Queue
다익스트라, 작업 스케줄링	PriorityQueue

 

별첨 일반 큐 방식

public int solution(String[][] book_time) {
    // 1. 입실시간 기준 정렬
    Arrays.sort(book_time, (a, b) -> toMinutes(a[0]) - toMinutes(b[0]));

    List<Queue<Integer>> rooms = new ArrayList<>();

    for (String[] time : book_time) {
        int start = toMinutes(time[0]);
        int end = toMinutes(time[1]) + 10; // 퇴실 후 청소 10분 포함

        boolean assigned = false;

        // 기존 방 중 사용할 수 있는 방 찾기
        for (Queue<Integer> room : rooms) {
            if (room.peek() <= start) { // 가장 마지막 예약 종료시간 + 10분 ≤ 현재 시작시간
                room.poll(); // 지난 예약 제거
                room.offer(end); // 현재 예약 추가
                assigned = true;
                break;
            }
        }

        // 기존 방으로 불가능하면 새 방 추가
        if (!assigned) {
            Queue<Integer> newRoom = new LinkedList<>();
            newRoom.offer(end);
            rooms.add(newRoom);
        }
    }

    return rooms.size();
}