155651. 호텔 대실

문제

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

프로그래머스

제한조건

풀이

import java.util.*;

class Solution {
    public int solution(String[][] book_time) {
        int answer = 0;
        
        List<int[]> tList = new ArrayList<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(String[] tArr : book_time) {
            int start = timeToMinute(tArr[0]);
            int end = timeToMinute(tArr[1]);
            
            tList.add(new int[]{start, end});
            
        }
        
        Collections.sort(tList, (o1, o2) -> o1[0] - o2[0]); // 시작시간 오름차순 정렬

        
        for(int[] t : tList) {
            int start = t[0];
            int end = t[1];
            if(pq.isEmpty()) {
                pq.offer(end);
                continue;
            }
            
            int beforeEnd = pq.peek();
            if(start>= beforeEnd + 10) {
                pq.poll();
                pq.offer(end);
            }
            else {
                pq.offer(end);
            }
            
        }
        
        answer = pq.size();
        return answer;
        
    
    }
    
    int timeToMinute(String t) {
        String[] tt = t.split(":");
        return Integer.valueOf(tt[0]) * 60 + Integer.valueOf(tt[1]);
    } 
}

회고

문제를 파악하면서 정렬이 중요하다고 판단했다. 그래서 우선순위 큐를 사용해서 문제를 풀었다. 큐에 들어가는 원소는 '룸'이다. 구체적으로 설명하자면 각 원소는 룸이고 값은 대실 종료 시간이다.

대실 시작 시간을 기준으로 book_time를 정렬시켰다. 그리고 각 대실 시작 시간을 우선 순위 큐의 첫 번째 원소(룸)에 들어갈 수 있는지 확인한다. 들어갈 수 없으면 나머지 원소(룸)에도 들어갈 수 없다. 왜냐하면 우선 순위 큐는 대실 종료 시간으로 오름차순 정렬되기 때문에, 첫 번째 원소와 비교해서 예약을 할 수 없는 시간이면, 나머지 원소는 첫 번째 원소보다 대실 종료 시간이 더 늦기 때문에 확인할 필요가 없다. 대신 큐에 원소(룸)을 추가한다.

 

이 문제는 쉽다고 느끼지 못했지만 정렬이 중요 포인트라고 판단했고, 우선순위 큐가 떠올라 바로 적용해봤다. 실패 없이 한번에 통과해서 뿌듯했다.