프로그래머스 - 호텔 대실(Java)

By on January 31, 2024

프로그래머스 - 호텔 대실(Java)

문제 링크 : 호텔 대실

문제 해결 접근법

이번 문제는 기본 적인 bfs 를 활용 해서 문제를 해결 했다.

규칙

  • 예약을 예약 시간이 빠른 순서 대로 정렬 하여 큐(bookingQ)에 입력 합니다.
  • 방 사용 시간을 확인할 스택 배열(useRoomList)을 생성 합니다.

  • 큐에서 예약을 하나씩 가져오면서 각 방의 이용 상태를 체크하고 필요에 따라 새로운 방을 배정하고, 이를 반복하여 이용할 수 있는 최소한의 방의 개수를 구합니다.

소스

public class 호텔대실 {
    private static final SimpleDateFormat sf = new SimpleDateFormat("HH:mm");
    public int solution(String[][] book_time) {
        int answer = 0;
        
        //예약 시간을 배열에 담아서 빠른 예약 시간 부터 정렬 한다.
        List<Room> books = new ArrayList<>();
        for (String[] strings : book_time) {
            long startBookTime = convertStringTimeToMilliseconds(strings[0]);
            long endBookTime = convertStringTimeToMilliseconds(strings[1]);
            books.add(new Room(startBookTime, endBookTime));
        }
        books.sort(Comparator.comparingInt(t -> Math.toIntExact(t.startTime)));

        //전체 예약을 담은 큐를 생성 한다.
        Queue<Room> bookingQ = new LinkedList<>(books);
        //방을 사용 시간을 체크 할 배열 스택을 생성 한다.
        List<Stack<Room>> useRoomList = new ArrayList<>();

        while (!bookingQ.isEmpty()){
            boolean use = false;
            //큐에서 예약을 하나 가져 온다.
            Room nowRoom = bookingQ.poll();
            //배열 스택을 체크 해서 사용중이면 새로운 방을 배정 한다.
            for (Stack<Room> rooms : useRoomList) {
                Room chkRoom = rooms.peek();
                if (addCleanRoomTime(chkRoom) <= nowRoom.startTime) {
                    rooms.pop();
                    rooms.add(nowRoom);
                    use = true;
                    break;
                }
            }
            if(!use){
                answer++;
                Stack<Room> rs = new Stack<>();
                rs.push(nowRoom);
                useRoomList.add(rs);
            }
        }

        return answer;
    }

    //종료시간 + 10분(청소 시간) 을 ms 로 계산
    private static long addCleanRoomTime(Room chkRoom) {
        return chkRoom.endTime + (10 * 60 * 1000);
    }

    //주어진 시간을 ms 로 변환 해서 처리
    private long convertStringTimeToMilliseconds(String s) {
        try {
            Date date = sf.parse(s);
            return date.getTime();
        } catch (ParseException e) {
            throw new RuntimeException(e);
        }
    }

    class Room{
        private long startTime;
        private long endTime;

        public Room(long startTime, long endTime) {
            this.startTime = startTime;
            this.endTime = endTime;
        }
    }
}

Back to blog