[Programmers] 155651. 호텔 대실 (java)

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

 

 

문제 파악

• 주어진 정보/입력
  • 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 한다.
  • 한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다음 손님들이 사용할 수 있다.
  • 입력: 예약 시각이 문자열 형태로 담긴 2차원 배열 book_time
    • book_time[i]는 [대실 시작 시각, 대실 종료 시각] 형태
• 해결해야 하는 문제
  • 코니에게 필요한 최소 객실의 수를 return하기

 

문제 풀이

Greedy + Priority Queue

import java.util.*;

class Solution {
    public int solution(String[][] book_time) {
        
        int N = book_time.length;
        
        // book_time을 대기 시작 시각이 빠른 순으로 정렬
        int[][] bookTime = new int[N][2];
        for (int i = 0; i < N; i++) {
            String[] startStr = book_time[i][0].split(":");
            bookTime[i][0] = Integer.parseInt(startStr[0]) * 60 + Integer.parseInt(startStr[1]);
            
            String[] endStr = book_time[i][1].split(":");
            bookTime[i][1] = Integer.parseInt(endStr[0]) * 60 + Integer.parseInt(endStr[1]);
        }
        Arrays.sort(bookTime, (b1, b2) -> b1[0] - b2[0]);
        
        // bookTime 순회하며 처리
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        List<Boolean> rooms = new ArrayList<>();
        for (int[] times : bookTime) {
            pq.add(times[1] + 10);
            
            if (!pq.isEmpty() && pq.peek() <= times[0]) {
                pq.poll();
            }
            else {
                rooms.add(true);
            }
        }
        
        return rooms.size();
    }
}

 

📊실행 결과

 

NOTE

 

• List의 set(int index, E element) 메서드는 지정한 인덱스의 요소를 새로운 값으로 바꾸는 메서드 -> 기존에 있던 값을 반환
• ArrayList + Collections.sort(collection) : 수동으로 정렬해야 함, O(logN)
• PriorityQueue : 요소를 넣을 때마다 자동으로 정렬 (Heap 구조), O(logN)
• PriorityQueue - offer(), poll(), peek()
• PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); 참고