[Programmers] 호텔 대실 / ⭕

프로그래머스

 

1. 제출 코드 (57분 32초 / Greedy)

import java.util.*;

class Solution {
    public int solution(String[][] book_time) {
        int answer = 0;
        PriorityQueue<String> pq = new PriorityQueue<>((o1, o2) -> {
            String[] s1 = o1.split(":");
            String[] s2 = o2.split(":");
            if(Integer.parseInt(s1[0]) != Integer.parseInt(s2[0])) {
                return Integer.parseInt(s1[0]) - Integer.parseInt(s2[0]);
            } else {
                return Integer.parseInt(s1[1]) - Integer.parseInt(s2[1]);
            }
        });
        
        Arrays.sort(book_time, (o1, o2) -> {
            String[] s1 = o1[0].split(":");
            String[] s2 = o2[0].split(":");
            if(Integer.parseInt(s1[0]) != Integer.parseInt(s2[0])) {
                return Integer.parseInt(s1[0]) - Integer.parseInt(s2[0]);
            } else {
                return Integer.parseInt(s1[1]) - Integer.parseInt(s2[1]);
            }
        });
        for(int i = 0; i < book_time.length; i++) {
            if(pq.isEmpty()) {
                pq.offer(book_time[i][1]);
            } else {
                if(calc_time(pq.peek(), book_time[i][0])) {
                    pq.poll();
                }
                pq.offer(book_time[i][1]);
            }
        }
        answer = pq.size();
        return answer;
    }
    
    static boolean calc_time(String s1, String s2) {
        String[] prev = s1.split(":");
        String[] curr = s2.split(":");
        int prev_time = Integer.parseInt(prev[0])*60 + Integer.parseInt(prev[1]);
        int curr_time = Integer.parseInt(curr[0])*60 + Integer.parseInt(curr[1]);
        if(prev_time + 10 <= curr_time) {
            return true;
        }
        return false;
    }
}

 

2. 구현 로직

1. 입실 시간을 기준으로 book_time 배열을 정렬
2. 우선순위 큐를 사용하여 사용중인 방중에 가장 빠른 퇴실 시간을 검색
3. 현재 순서의 시작 시간과 퇴실 시간을 비교하여 퇴실 시간이 더 빠른 경우 우선순위 큐에서 poll()
4. 위 과정을 반복하고 마지막에 우선순위 큐에 남아있는 size()를 return하여 정답 추출

 

3. 유의할 점

• 퇴실 시간과 현재 시작 시간을 비교할 때, 분으로 변환하지 않고 했는데 일부 테스트 케이스에서 오류가 났다.
• 생각을 해봤는데 +10분을 해주면서 시간이 바뀌는 경우가 있는데 이것을 고려해서 풀어야 한다.