Lv 4. 호텔 방 배정

 

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

프로그래머스

 

 

 

📌 자바(Java)로 푸는 호텔 방 배정 문제 - 프로그래머스 🏨

🔎 문제 개요

프로그래머스 - 호텔 방 배정 문제입니다.
호텔에는 k개의 방이 있으며, 손님이 원하는 방을 요청하면 비어 있으면 배정하고,
비어있지 않다면 가장 가까운 빈 방을 배정해야 합니다.
🚪 여러 손님이 들어오면서 빠르게 배정하는 것이 핵심입니다.

---

💡 예제 입력

long k = 10;
long[] room_number = {1, 3, 4, 1, 3, 1};

💡 예제 출력

[1, 3, 4, 2, 5, 6]

➡ 요청된 방이 이미 배정되었으면, 가장 가까운 빈 방을 찾아 배정

---

🛠 알고리즘 접근 방식

이 문제를 해결하기 위해 유니온-파인드(Union-Find) + 경로 압축(Path Compression) 을 활용합니다.

✏️ 주요 고려 사항

✔ 손님이 원하는 방이 비어있다면 즉시 배정
✔ 이미 배정된 방이면, 가장 가까운 빈 방을 찾아 배정
✔ 경로 압축(Path Compression) 기법을 사용하여 빠르게 빈 방을 찾음
✔ 각 방 번호를 HashMap<Long, Long>을 활용하여 관리

---

🔹 Java 코드 해설

import java.util.*;

class Solution {

    HashMap<Long,Long> status = new HashMap<>();

    public long[] solution(long k, long[] room_number) {
        int len = room_number.length;
        long[] answer = new long[len];

        for (int i = 0; i < len; i++) {
            answer[i] = find(room_number[i]);
        }
        return answer;
    }
    
    long find(long room_num) {
        if (!status.containsKey(room_num)) {
            status.put(room_num, room_num + 1);
            return room_num;
        }
        long empty = find(status.get(room_num));  // 경로 압축
        status.put(room_num, empty + 1); // 부모를 업데이트
        return empty;
    }
}

 

---

🔍 코드 설명

📌 1. 손님이 요청한 방을 확인

if (!status.containsKey(room_num)) {
    status.put(room_num, room_num + 1);
    return room_num;
}

✔ 비어있다면 해당 방을 배정하고, 다음 빈 방을 갱신
✔ 처음 방문하는 방은 그대로 배정

---

📌 2. 경로 압축을 활용한 빈 방 찾기

long empty = find(status.get(room_num));  // 경로 압축
status.put(room_num, empty + 1); // 부모를 업데이트
return empty;

✔ 이미 배정된 방이면 가장 가까운 빈 방을 찾음
✔ 경로 압축(Path Compression) 기법을 활용하여 빠르게 업데이트

---

🏆 정리

✅ 핵심 포인트

✔ 유니온-파인드(Union-Find) 알고리즘을 사용하여 최적화
✔ 경로 압축(Path Compression)으로 빠르게 빈 방 찾기
✔ HashMap을 활용하여 O(1)에 가깝게 처리

🎯 이 알고리즘의 장점

✅ 빠르게 가장 가까운 빈 방을 찾을 수 있음
✅ O(N log N) 복잡도로 최적화된 풀이 가능
✅ 대량의 요청이 들어와도 빠르게 처리 가능

---

이 글이 도움이 되셨다면 좋아요와 공유 부탁드립니다! 😊