프로그래머스 호텔 대실(lvl2) 풀어보기

문제링크

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

프로그래머스

---

문제 핵심

호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다음 손님들이 사용할 수 있습니다.
예약 시각이 문자열 형태로 담긴 2차원 배열 book_time이 매개변수로 주어질 때, 코니에게 필요한 최소 객실의 수를 return 하는 solution 함수를 완성해주세요.

• 시각은 HH:MM 형태로 24시간 표기법을 따르며, "00:00" 부터 "23:59" 까지로 주어집니다.
  • 예약 시각이 자정을 넘어가는 경우는 없습니다.
  • 시작 시각은 항상 종료 시각보다 빠릅니다.

---

알고리즘

-예약시간 오름차순으로 정렬

예약시작시간과 이전 종료시간+청소시간비교

가능하다면 해당호실에 마지막 종료시간 변경

불가능하다면 새 호실 생성

---

코드

 public static int solution(String[][] book_time) {

        int answer = 0;

        Arrays.sort(book_time, (a, b) -> a[0].compareTo(b[0]));

        System.out.println(Arrays.deepToString(book_time));

        Map<Integer, List<String[]>> rooms = new LinkedHashMap<>();

        Map<Integer, LocalTime> roomsLast = new LinkedHashMap<>();

        for (String[] bt : book_time) {

            LocalTime sTime = LocalTime.parse(bt[0]);

            LocalTime eTime = LocalTime.parse(bt[1]);

            List<String[]> times = new LinkedList<>();

            System.out.println("현재총객실수:" + rooms.size());

            if (rooms.isEmpty()) {

                System.out.println("최초입실");

                times.add(new String[] { sTime.toString(), eTime.toString() });

                rooms.put(1, times);

                roomsLast.put(1, getCleanTime(eTime));

                continue;

            }

            int roomn = -1;

            for (Map.Entry<Integer, LocalTime> entry : new LinkedHashMap<>(roomsLast).entrySet()) {

                Integer room = entry.getKey();

                LocalTime time = entry.getValue();

                System.out.println(room + "번 객실 입실가능시간" + time + "다음입실시간: " + sTime);

                if (time.isBefore(sTime) || time.equals(sTime)) {

                    System.out.println("사용할수있는 객실 발견");

                    roomn = room;

                    break;

                }

            }

            if (roomn == -1) {

                System.out.println("사용할수있는객실없음");

                int newRoom = rooms.size() + 1;

                times.add(new String[] { sTime.toString(), eTime.toString() });

                rooms.put(newRoom, times);

                roomsLast.put(newRoom, getCleanTime(eTime));

                continue;

            }

            System.out.println("사용할수있는객실저장");

            times = rooms.get(roomn);

            times.add(new String[] { sTime.toString(), eTime.toString() });

            rooms.put(roomn, times);

            roomsLast.put(roomn, getCleanTime(eTime));

        }

        rooms.forEach((key, value) -> {

            System.out.println(key + "번 객실 = " +

                    value.stream()

                            .map(Arrays::toString)

                            .toList());

        });

        System.out.println(roomsLast);

        answer = rooms.size();

        return answer;

    }

    public static LocalTime getCleanTime(LocalTime eTime) {

        LocalTime cleanTime = eTime.plusMinutes(10);

        int cleanMinutes = eTime.getHour() * 60 + eTime.getMinute() + 10;

        if (cleanMinutes >= 24 * 60) {

           System.out.println("퇴실시간이 자정을넘음");

           cleanTime = LocalTime.of(23, 59);

        }

        return cleanTime;

    }

 

---

결과

---

gpt피드백

-개선 가능한 알고리즘은 우선순위 큐(PriorityQueue)야. 객실의 다음 입실 가능 시간을 오름차순으로 관리하면, 가장 빨리 비는 객실만 확인하면 돼. 정렬을 포함해 전체 

O(Nlog⁡N)O(N\log N)O(NlogN)으로 줄일 수 있어.

다만 현재 풀이도 통과했고, 객실을 직접 배정하는 방식 자체는 맞아.

 

 

 

---

배운점과느낀점

-종료시간이 +10분이 24시를 넘어가는 시간을

생각하지 못해서 조금 애먹었다 gpt반례요청으로 풀었다

gpt 개선 코드를 보니 우선순위큐를 사용해 획기적으로 줄어든게 참 대단하다