공부하는 식빵맘 👱‍♀️

공부하는 식빵맘 👱‍♀️

반갑습니다 :)

[C++로 풀이] 호텔 방 배정 (Union-Find) ⭐⭐⭐⭐

Date:     Updated:

카테고리:

태그:

📌 호텔 방 배정

난이도 ⭐⭐⭐⭐

🚀 문제

image

image


🚀 내 풀이

k 가 매우 크다. 그러므로 방 하나하나를 선형으로 순회하는 \(O(k)\) 만으로도 시간 초과가 될 것이다.

🔥 이분 탐색 풀이 ❌

#include <string>
#include <vector>

using namespace std;

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;
    vector<bool> checked(k + 1);

    for (auto num : room_number) {
        long long start = 1;
        long long end = k;
        long long mid = 0;
        long long room = 0;
        while (start < end) {
            mid = (start + end) / 2;
            if (mid < num)
                start = mid + 1; // mid 는 답이 될 수 없음
            else {
                if (!checked[mid])
                    room = mid;
                end = mid; // mid 는 답이 될 수 있는 가능성이 있음
            }
        }
        checked[room] = true;
        answer.push_back(room);
    }
    return answer;
}

일단 방의 개수인 k의 최대값이 굉장히 크기 때문에 처음엔 이분 탐색을 생각했었다. 게다가 방을 찾았다가 빈 방이 아니면 빈방이 아닌 다음 방을 선택하기 때문에 직관적으로 lower_bound 를 생각했었다.

1 ~ k 개(이 자체만으로 정렬된 상태)의 방에서 이분 탐색으로 답을 찾아나가는데, 문제에서 원하는 방 혹은 원하는 방보다 큰 번호의 방을 배정받는다고 하였으니 mid가 손님이 원하는 방인 num 보다 작은 값이라면 절대 답이 될 수 없다. 반대로 mid 가 손님이 원하는 방인 num과 같거나 혹은 크다면 답의 후보가 될 수 있으므로 현재의 mid 가 빈 방이 아니라면 room 에 저장해두는 식으로 했다. 그리고 while 문이 끝나면 가장 최근에 없뎃된 room 에 배정하는 식으로 코드를 짰다.

이 코드의 문제점

10 개의 방에서 1,2,3,4,5 방이 이미 배정되었다고 가정해보자. 이런 상황에서 1 번방에 묵고 싶다는 손님이 있다면 6 번 방에 배정을 받는게 옳을 것이다. 그러나 위 풀이로는 6번이라는 답을 도출하지 못한다. 이분 탐색을 한다는 것은, 절반의 범위에서 답을 찾겠다는 것이다. 한번 범위가 절반으로 좁혀지만 그 이외에 소위 “잘린 범위”의 값들은 답이 될 수 없으며 그 범위를 다시 답이 될 수 있는 후보로 삼을 방법도 없다. 손님이 원하는 방은 1 번이기에 범위는 1 ~ 10 에서(mid = 5) 1 ~ 5 (mid = 3) 이 될 것이다. 답은 6 인데도 이렇게 절반의 범위가 좁혀지며 6 은 답의 범위에서 제외되버린다. 1 ~ 5 번방이 모두 차있다는 것을 알고난 후엔 이미 늦었다. 그래서 이분 탐색으로는 이 문제를 풀 수 없다고 결론 짓게 되었다. ㅠ ㅠ

손님이 원하는 방이 비어있지 않다면 어느 방을 배정해야할지를 그 정보를 늘 가지고 있어야 하며 효율적으로 업데이트가 되는 방법을 택해야 한다. 즉, 1->2->3->4->5->6 이런 식으로 빈 방인 6번 방을 찾는 것이 아니라, 1~5번 방은 비어있지 않으니 6번방으로 가라는 정보를 가지고 있어야 한다. 그래야 손님이 1~5번 방으로 가고 싶어하면 \(O(k)\) 순회를 할 필요 없이 바로 6 번방으로 가면 되겠구나 하고 알 수 있도록! 효율적이라는 것은 \(O(k)\)가 되지 않으면서, a 방이 배정이 되었을 때 다음엔 a 방으로 가도록 value 가 정해져있던 방(key)들의 정보를 업데이트 한다는 면에서.


🔥 Union-Find 풀이 ⭕

Union-Find 알고리즘에 대해서는 (C++) Union-Find 알고리즘 포스팅 한적이 있다. 참고 :)

  • 해시맵으로 배정되야 할 방을 관리한다.
    • Key : 방 번호
    • Value : 해당 방(key)로 배정받고자 할 때 실제로 배정해야할 다음 빈 방
      • 예를 들어 1,2,3,4,5 방이 꽉 차있다면 map[1] 의 value 는 6 이 되어야 한다.
  • Union-Find 알고리즘에 사용되는 getParent 함수를 사용하여 해시맵을 타고 타고 가서 다음으로 가능한 빈방을 찾아내 리턴 받는다.
    • value
      • 0 이면 빈방
      • 0 이 아니면 해당 key (방)은 배정 되었으니 이 방으로 가서 배정받으세요~ 라는 의미
    • 재귀 호출 👉 빈 방을 찾는다.
      • 데이터 상황에서 각자 방마다 “이 방은 배정 되었으니 value 방으로 가세요” 하는 방으로 타고 타고 간다. 타고 타고 갈 수 있다는 것은 현재 그 전의 방들은 빈방이 아닌 곳을 가라고 가리키는 것이나 마찬가지이므로 정보 업데이트가 필요하다.
      • 그렇게 타고 타고 가다가 빈 방을 드디어 찾아내면 재귀호출 종료 후 해당 빈방 리턴값을 가지고 Back 시작
    • 재귀 호출에서 돌아오는 과정에서 👉 지나온 잘못된 정보들을 알려준 방들에게 찾아낸 빈방 리턴값으로 대입을 해주어 정정해준다.


2 차 풀이 ⭕

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

unordered_map<long long, long long> room; // key : 방 번호  value : 0 이면 빈방, a 이면 이 방은 빈방이 아니며 a 번 방으로 가라는 의미(업뎃 전 정보인 상태일 수 있음)
long long GetEmptyRoom(long long n)
{
    if (room[n] == 0) return n; // 빈 방을 찾았다면 n 을 리턴한다. 
    return room[n] = GetEmptyRoom(room[n]); // 재귀호출을 끝내고 돌아오는 과정에서 타고 올라오기 전의 방들에게도 n 으로 업데이트 해준다.
}

vector<long long> solution(long long k, vector<long long> room_number){
    vector<long long> answer;

    for (auto num : room_number){
        long long emptyRoom  = GetEmptyRoom(num); // 손님은 num 방 가고 싶어할 때 손님이 갈 수 있는 빈 방
        answer.push_back(emptyRoom);
        room[emptyRoom] = emptyRoom + 1; // 해당 방은 배정 되었으므로 다음 방으로 일단 지정해놓는다. (틀린 정보라도 나중에 GetEmptyRoom 함수 재귀호출에서 돌아오는 과정에서 정정 된다.)
    }
    return answer;
}

코드 참고 https://regularmember.tistory.com/193

image

room_number : {1, 3, 4, 1, 3, 1}

  • 1 번 방을 배정 받고 싶어하는 손님 + 현재 호텔 방 상황 { 0, 0, 0, 0, 0, 0 }
    • 빈 방 찾기
      • room[1] = 0 👉 1 번이 빈 방이므로 1 번으로 배정 return 1
    • 빈 방에 배정한 후 해당 방은 이제 더 이상 배정 받을 수 없으므로 다음 방을 value 로 한다.
      • room[1] = 2
  • 3 번 방을 배정 받고 싶어하는 손님 + 현재 호텔 방 상황 { 2, 0, 0, 0, 0, 0 }
    • 빈 방 찾기
      • room[3] = 0 👉 3 번이 빈 방이므로 3 번으로 배정 return 3
    • 빈 방에 배정한 후 해당 방은 이제 더 이상 배정 받을 수 없으므로 다음 방을 value 로 한다.
      • room[3] = 4
  • 4 번 방을 배정 받고 싶어하는 손님 + 현재 호텔 방 상황 { 2, 0, 4, 0, 0, 0 }
    • 빈 방 찾기
      • room[4] = 0 👉 4 번이 빈 방이므로 4 번으로 배정 return 4
    • 빈 방에 배정한 후 해당 방은 이제 더 이상 배정 받을 수 없으므로 다음 방을 value 로 한다.
      • room[4] = 5
  • 1 번 방을 배정 받고 싶어하는 손님 + 현재 호텔 방 상황 { 2, 0, 4, 5, 0, 0 }
    • 빈 방 찾기
      • room[1] = 2 👉 1 번 방은 빈 방이 아님. 2 번방으로 가라고 했으니 2 번방으로 가본다.
        • room[2] = 0 👉 2 번이 빈 방이므로 2 번으로 배정 return 2
      • room[1] = 2 (돌아오면서 정정)
    • 빈 방에 배정한 후 해당 방은 이제 더 이상 배정 받을 수 없으므로 다음 방을 value 로 한다.
      • room[2] = 3
  • 3 번 방을 배정 받고 싶어하는 손님 + 현재 호텔 방 상황 { 2, 3, 4, 5, 0, 0 }
    • 빈 방 찾기
      • room[3] = 4 👉 3 번 방은 빈 방이 아님. 4 번방으로 가라고 했으니 4 번방으로 가본다.
        • room[4] = 5 👉 4 번 방은 빈 방이 아님. 5 번방으로 가라고 했으니 5 번방으로 가본다.
          • room[5] = 0 👉 5 번이 빈 방이므로 5 번으로 배정 return 5
        • room[4] = 5 (돌아오면서 정정)
      • room[3] = 5 (돌아오면서 정정)
    • 빈 방에 배정한 후 해당 방은 이제 더 이상 배정 받을 수 없으므로 다음 방을 value 로 한다.
      • room[3] = 6
  • 1 번 방을 배정 받고 싶어하는 손님 + 현재 호텔 방 상황 { 2, 3, 5, 5, 6, 0 }
    • 빈 방 찾기
      • room[1] = 2 👉 1 번 방은 빈 방이 아님. 2 번방으로 가라고 했으니 2 번방으로 가본다.
        • room[2] = 3 👉 2 번 방은 빈 방이 아님. 3 번방으로 가라고 했으니 3 번방으로 가본다.
          • room[3] = 5 👉 3 번 방은 빈 방이 아님. 5 번방으로 가라고 했으니 5 번방으로 가본다.
            • room[5] = 6 👉 5 번 방은 빈 방이 아님. 6 번방으로 가라고 했으니 6 번방으로 가본다.
              • room[6] = 0 👉 6 번이 빈 방이므로 6 번으로 배정 return 6
            • room[5] = 6 (돌아오면서 정정)
          • room[3] = 6 (돌아오면서 정정)
        • room[2] = 6 (돌아오면서 정정)
      • room[1] = 6 (돌아오면서 정정)
    • 빈 방에 배정한 후 해당 방은 이제 더 이상 배정 받을 수 없으므로 다음 방을 value 로 한다.
      • room[6] = 7
  • 종료 후 호텔 방 상황 { 6, 6, 6, 5, 6, 7 }

value 가 같다는 것 key 들은 같은 루트 노드를 가진 집합에 속한다고 볼 수 있다.


3 차 풀이 ⭕

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

unordered_map<long long, long long> room;
long long GetEmptyRoom(long long n)
{
    if (room[n] == 0) return n;
    return room[n] = GetEmptyRoom(room[n]);
}
vector<long long> solution(long long k, vector<long long> room_number){
    vector<long long> answer;

    for (auto num : room_number){
        if (room[num] == 0){ // 빈 방이라면 
            answer.push_back(num);
            room[num] = GetEmptyRoom(num + 1); // num + 1 이 빈방이라면 num + 1 아니라면 num + 1 보다 큰 것 중에 가장 작은 빈 방 찾아옴
        }
        else{ // 빈 방이 아니라면 
            long long next_num = GetEmptyRoom(num);
            answer.push_back(next_num);
            room[next_num] = GetEmptyRoom(next_num + 1); // num + 1 이 빈방이라면 num + 1 아니라면 num + 1 보다 큰 것 중에 가장 작은 빈 방 찾아옴
        }
    }
    return answer;
}

image

코드 참고 https://yabmoons.tistory.com/486

위와 같이 풀 수도 있다. 위 풀이는 빈 방일 때, 빈 방이 아닐 때로 케이스를 나누고(빈 방이면 바로 배정한다.) room[num] Value 를 정하는 과정에서도 현재 시점에서 정확한 정보로 대입을 한다. 이 과정에서도 GetEmptyRoom 호출하여서!


해시맵을 쓰지 않고 배열을 쓰면 “메모리 초과” 발생 😱

#include <string>
#include <vector>

using namespace std;

vector<long long> room;
long long GetEmptyRoom(long long n)
{
    if (room[n] == 0) return n;
    return room[n] = GetEmptyRoom(room[n]);
}

vector<long long> solution(long long k, vector<long long> room_number){
    vector<long long> answer;
    room.resize(k + 1);

    for (auto num : room_number){
        if (room[num] == 0){
            answer.push_back(num);
            room[num] = GetEmptyRoom(num + 1);
        }
        else{
            long long next_num = GetEmptyRoom(num);
            answer.push_back(next_num);
            room[next_num] = GetEmptyRoom(next_num + 1);
        }
    }
    return answer;
}

image

해시맵이 아닌, 배열(vector)를 쓰면 메모리 초과가 발생한다. k 의 최대값이 무려 1 조다 (..) 그렇기 때문에 배열로 관리를 하면 long long 을 1 조개 담을 수 있는 아주 큰 용량을 할당받는 것과도 같다. room_number의 최대 크기는 200,000 이기 떄문에 수 많은 방에 비해 손님들이 원하는 방의 후보의 수는 훨씬 적을 것이다. 즉, 쓰이지 않는 방도 굉장히 많을 수 있다는 것이다. 배열의 인덱스를 통한 임의 접근도 O(1) 로 아주 빠르지만 메모리 낭비가 대단하므로 해시맵을 사용하는 것이 좋겠다.


🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기

댓글 남기기

최근 글 10 개 :)