ココアホテルの部屋を手配します

質問:https://programmers.co.kr/learn/courses/30/lessons/64063
[1.理解]
近いホテルの部屋が手配されている場合は、それより大きくて手配されていない部屋を選ぶことができます.
[2.近接]
まず、可能なホテルの部屋数は最大20万個で、この時の番号は0から10^12です.この場合はホテルの部屋番号の並びでは表示できません.したがって,資料構造では,ハッシュツリーベースのコンテナに値を格納するか,リストを使用するか,動的配列ベースのコンテナを使用するかが正しい.通常のフルアクセス(シーケンスアクセス)シーケンスアクセスを使用して空き部屋を探す場合は、時間の複雑さを通過できないため、検索の効率が重要です.大まかに二つの方法を考える.
- 1. ダイナミック配列+二分ナビゲーション
実装ロジックは次のとおりです.手配した部屋番号は昇順に並べられています.
1.まず部屋のレイアウトでお客様が望む部屋を探す
2.お客様が希望する部屋が空いていれば、その部屋を手配します.
3.部屋が空いていなければ、その部屋を起点に、空き部屋があるかどうかを並べて探します.
4.手配した部屋を並べる.
この場合、配列された該当点に空き部屋があるかどうかを判断するために、容量(範囲内に入ることができる部屋の数)とsize(実際に入る部屋の数)が使用される.例:
roomの[0,2]には、room[0]=1、room[1]=2、room[2]=4がある.
このときsizeは3です.(この範囲に3つの値を入力できます.)
そして容量は4です.[[room[0],room[2]であるため、1、2、3、および4個の値を含むことができる.)
すなわち、容量と大きさが異なる場合はその範囲内に空き部屋が存在し、同じ場合は空き部屋は存在しない.
ぶんせき
まず,空き部屋を探すのに要する時間の複雑さはO(logn)である.しかし,動的配列の中間点挿入に必要な複雑さはO(N)である.また,2回の二分検索を用いたため,コードの複雑さも高い.
- 2. ハッシュマッピング+Union Find
ハッシュマッピングpmapの場合、keyは部屋の番号であり、valueは部屋の親部屋、すなわちその部屋に近づくと押し出される部屋の番号である.例:pMap[4]は5を指し、割り当てられた部屋が1,2,4で同期していると仮定する.
論理全体は次のとおりです.
1.お客様が希望する部屋がある場合(pMapに該当するキー値がない場合)
割り当て、pMap[num]=+num.△次の部屋の場所を教えてあげます.
2.お客様が自分の希望する部屋がない場合は、ユニオンフィールドで空き部屋があるまで再探索します.同期します.見つかった部屋について1番のレッスンを行います.
ぶんせき
Union Findでは、ナビゲートするたびに、ナビゲートしたノードを同期します.DPのメモリ割り当てのように、次の手順を実行する必要があります.1号に空き部屋があるか確認する際、探索中にHashMapを使うのはO(1)です.また、空き部屋がなければ、その空き部屋を探す過程はユニオンツリーのDepthに比例する.一度のブラウズでは,Depthに属するブラウズ中のノードが一度に同期し,Memorizationの効果が見られる.このことから,すべての部屋を割り当てるのに要する時間はO(N)に比例することが分かる.
[3.実施]

ダイナミックアレイ+デュアルナビゲーション

#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll> hotel; //고객이 예약한 방이 번호별 정렬되있음.
bool isRange(int end, int start); //해당 범위에 빈방이 있는지 체크
pair<int, bool> process1(ll &room); //고객이 원하는 지점에 빈방이 있는지 체크및 없다면 방의 위치 반환 
ll process2(int start); //해당지점의 방위치부터 이분탐색으로 빈방의 위치를 찾음 

bool isRange(int end, int start)
{
    ll capacity_ = hotel[end] - hotel[start]; //수용가능공간
    ll size_ = end - start; //현재 차있는공간
    return capacity_ != size_; //빈방이있다면
}
pair<int, bool> process1(ll &room) //int=위치 bool=true일시 작업끝남(방에들어감),false:방 위치 찾지못함
{
    pair<int, bool> result;
    int left = 0;
    int right = hotel.size() - 1;
    while (left < right)
    {
        int mid = (left + right) >> 1;
        if (hotel[mid] >= room)
            right = mid;
        else
            left = mid + 1;
    }
    if (hotel.empty() || hotel.back() < room) //비어있거나 더큰값일시
    {
        hotel.push_back(room);
        result = {0, true};
    }
    else //비어있지않을시
    {
        if (hotel[left] == room) //방이있을시
        {
            result = {left, false}; //있다면 해당방의 [위치,true] return
        }
        else
        {
            if (hotel[left] > room)
            {
                hotel.insert(hotel.begin() + left, room);
            }
            else
            {
                hotel.push_back(room);
            }
            result = {0, true}; //없다면 hotel에 집어넣고 [0,true] return
        }
    }
    return result;
}
ll process2(int start)
{
    ll result;
    int left = start;
    int right = hotel.size() - 1;
    while (left < right)
    {
        int mid = (left + right) / 2;
        if (isRange(mid, start)) //해당범위안에 남은 방이있을경우
            right = mid;
        else
            left = mid + 1;
    }
    if (isRange(left, start))
    {
        result = hotel[left - 1] + 1;
        hotel.insert(hotel.begin() + left, result);
    }
    else{
        result=hotel[left]+1;
        hotel.push_back(result);
    }
    return result;
}
vector<ll> solution(ll k, vector<ll> room_number)
{
    vector<ll> answer;
    for (auto room : room_number)
    {
        pair<int, bool> info = process1(room);
        if (!info.second) //해당지점에 빈방이 없다면
        {
            room = process2(info.first); //고객원하는지점부터 빈방찾기
        }
        answer.push_back(room); //새로찾은 방위치 집어넣기
    }
    hotel.clear();
    return answer;
}

海図+Union Find

#include<bits/stdc++.h>
#define ll long long
using namespace std;
unordered_map<ll,ll> P;
ll find(ll room){
    if(P[room]==0) return room; 
    else return P[room]=find(P[room]);
}
vector<ll> solution(ll k, vector<ll> room_number)
{   vector<ll> answer;
    for(auto number:room_number){
        ll room=find(number);
        P[room]=room+1;
        answer.push_back(room);
    }   
    return answer;
}