문제: https://programmers.co.kr/learn/courses/30/lessons/64063
[1.이해]
접근할려는 호텔방이 이미배정되어있으면 그것보다 크고 배정되지 않은 방을 선택하면된다.
[2.접근]
먼저 가능한 호텔방의 갯수는 최대 20만개이고 이때 번호는 0부터 10^12이다. 이럴한 경우는 호텔방번호에 따른 배열로 표현할 수는 없다. 따라서 자료구조로는 해쉬트리기반 컨테이너에 값을 저장하던지 리스트,동적배열 기반 컨테이너를 사용하는게 옳아보인다. 일반적인 완전탐색의 (순차접근)sequential access로 빈방을 찾는다면 시간복잡도를 통과하지 못하는데 탐색의 효율성이 중요하다. 크게 두가지 방법이 떠오른다.
- 1. 동적배열+이분탐색
구현 로직은 다음과 같다. 배열에는 배정한 방의 넘버들이 오름차순 정렬되어 있다.
1. 먼저 배열에 고객이 원하는 방이 있는지 이분탐색
2. 고객이 원하는 방이 비어 있다면 그 방을 배정해준다.
3. 방이 비어있지 않을 경우는 그방을 시작점으로 해서 배열에서 빈방이 있는지 이분탐색한다.
4. 배정한 방에 대하여 배열에 추가한다.
이때 배열의 해당지점에서 빈방이 있는지 없는지를 확인하기 위해서는 capacity(범위내에 들어갈 수 있는 방의갯수) 와 size(실제 들어가 있는 갯수)를 이용한다. 예를들면 다음과 같다.
room의 [0,2]에 대하여 room[0]=1, room[1]=2, room[2]=4가 있다.
이때 size는 3이다.(해당범위에서 3개의 값을 넣을 수 있으므로)
그리고 capacity는 4이다. [[room[0], room[2]]이므로 1~4사이의 값 1,2,3,4가 들어갈 수있으므로)
즉, capacity와 size가 같지않다면 해당범위 내에 빈방이 존재하고, 같다면 빈방이 존재하지 않는것이다.
분석
먼저 빈방을 찾는데 걸리는 시간복잡도는 O(logN)이다. 하지만 동적배열의 중간지점에 Insert하게 되는데서 걸리는 복잡도가 O(N)이다.또한 두번의 이분탐색을 사용하므로 코드의 복잡성또한 비교적 높다.
- 2. 해쉬맵+유니온파인드
해쉬맵 pMap의 경우 key는 방의 번호이고, value의 경우 해당방의 부모room, 즉 해당 방에 접근할경우 밀려지게된 방의 번호이다. 예를 들면 다음과 같다. 배정된 방이 1,2,4가 있을때 동기화가 되었다는 가정하에 pMap[1], pMap[2]는 3을 가르키고 있다고 pMap[4]는 5를 가르키고 있다.
전체 로직은 다음과 같다.
1.고객이 원하는 방이 있을시(pMap에 해당 키값이 없을 경우)
배정해주고 pMap[num]=++num을 해준다.(다음방의 위치알려준다.)
2.고객이 원하는 방이 없을시 유니온파인드 방식으로 빈방이 있을때까지 재귀적으로 탐색한다. 이때 동기화를 시켜줘야한다. 찾은방에 대하여 1번 과정을 진행해준다.
분석
유니온 파인드의 경우 탐색할때마다 탐색되는 노드들에 관해서 동기화를 시켜줘야 한다. 마치 DP의 메모리제이션과 비슷한데 다음과정을 해야 효율적이다. 1번의 빈방이 없는지 확인시 탐색과정에서 HashMap을 사용하기에 O(1)이다. 또한 빈방이 없을경우 해당 빈방을 찾는 과정이 Union트리의 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;
}- 해쉬맵+유니온파인드
#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;
}