[LV4] 호텔 방 배정

1. 문제

1) 문제 링크

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

코딩테스트 연습 - 호텔 방 배정

 

2) 설명

   사용자들이 원하는 방의 배열이 주어지고 순서대로 사용자들이 원하는 방에 배정한다.

이미 방이 사용 중이라면 원하는 방보다 높은 숫자의 빈 방 중 가장 낮은 빈 방을 배정받는다.

배정받은 방의 번호들의 배열을 리턴한다.

2. 풀이

1) 알고리즘

    : Solution 1 : set 사용

      Solution 2 : map, find 사용

 

2) 풀이 설명

  풀이 1. set 사용

일단 데이터 타입들이 long long이어서 효율성 문제가 있겠거니 생각했다.

효율성은 나중에 생각하고 일단 풀어보자 생각해서 set을 사용해서 풀어봤다.

 

1. get_allocated_room 함수를 통해 방을 배정받는다.

2. 원하는 방이 이미 배정된 방이라면 다음 방(target_room + 1)을 재귀적으로 확인한다.

3. 배정받는 방은 모두 room_set에 넣어준다.

 

알고리즘은 맞지만 예상대로 효율성을 통과하지 못했다.

왜냐하면 탐색할 때마다 room_set을 탐색해야 하는데 이 탐색이 원하는 방 + 1씩 증가하면서 계속 탐색하기 때문이다.

만약 1~1000,000,000 번 방이 다 꽉 차있고 다음 사람이 1번방을 원한다면 1~1000,000,000번 방을 set에서 찾아봐야 하기 때문이다...

그래서 다른 방법을 생각해봤는데 딱히 안 떠올라서 다른 풀이들을 약간 참고했다.

 

   풀이 2. map, find 사용

set을 사용할 때와 엄청나게 다른 풀이는 아니다. 다만 union-find 알고리즘 일부가 추가되었을 뿐이다.

room_map에는 key는 방 번호이고 value는 (비어있다면 0, 이미 배정된 방이라면 다음에 배정될 수 있는 방 번호) 이 된다.

그래서 탐색할 때마다 이 맵을 업데이트 해준다.

예를 들어 room_map 상황이 다음과 같다고 가정해본다.

{

    1 : 4,

    2 : 4,

    3 : 4,

}

이 상황에서 다음 사람이 2번 방을 원한다면 get_allocated_room 함수에서는

room_map[2]은 0이 아니므로 배정된 방이구나. -> 4번 방으로 가라네? 하고 get_allocated_room(4)를 호출한다.

그리고  room_map[4]는 0이니까 배정된 거네. 하고 4번 방을 리턴한다.

그러면 4번 방은 배정이 된 거니까 그 다음 방인 5번 방이 room_map[4]에 배정된다.

그래서 room_map은 다음과 같이 바뀐다.

{

    1 : 4

    2 : 4

    3 : 4

    4 : 5

}

그리고 다음에 2번방을 원하는 사람이 왔을 때 2 -> 4 -> 5의 탐색 과정을 다시 거치지 않도록 room_map[2]도 5로 업데이트 해준다. (어차피 get_allocated_room 함수는 재귀적으로 돌아가고 배정하는 건 그냥 한 줄 추가하는 거라 시간복잡도에 큰 영향은 없다. 즉 탐색 과정을 줄여서 얻는 속도 절감분이 room_map 업데이트를 위해 한 줄 추가해서 얻는 증가분보다 훨씬 크다)

그러면 room_map은 다시 다음과 같이 바뀐다.

{

    1 : 4,

    2 : 5,

    3 : 4,

    4 : 5

}

물론 1번이나 3번 방을 원하는 사람이 오면 1 -> 4 -> 5 나 3 -> 4 -> 5의 과정을 더 거쳐야하지만 2번 방에서만큼은 확실히 다음 탐색 때 속도를 줄여줄 수 있다.

또한 room_map이 다음 상황일 때는 

{

    1 : 2,

    2 : 3,

    3 : 4,

    4 : 5,

    ... (5 ~ 999999)

    1000000 : 0

}

3번 방을 원하는 사람이 왔을 때 3 -> 4 -> ... -> 1000000까지 탐색해야하지만 중간에 4번 방을 찾는 사람이 있어서 room_map[4] 값을 업데이트 해줬었다면, 즉 room_map이 다음과 같은 상황이라면

{

    1 : 2,

    2 : 3,

    3 : 4,

    4 : 1000000,

    ... (5 ~ 999999)

    1000000 : 0

}

3 -> 4 -> 1000000 으로 훨씬 단축시킬 수 있다.

 

이렇게 함수를 재귀적으로 돌려서 효율성 테스트까지 통과시킬 수 있었다.

3. 코드

//SOLUTION 1 : SET 사용
#include <vector>
#include <set>

using namespace std;

set<int> room_set;

long long get_allocated_room(long long target_room){
    if(room_set.find(target_room) == room_set.end()){
        return target_room;
    } else {
        return get_allocated_room(target_room + 1);
    }
}

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;
    for(int i=0;i<room_number.size();i++){
        long long allocated_room = get_allocated_room(room_number[i]);
        answer.push_back(allocated_room);
        room_set.insert(allocated_room);
    }
    return answer;
}

//SOLUTION 2 : MAP, FIND 사용

#include <vector>
#include <map>

using namespace std;

map<long long, long long> room_map;

long long get_allocated_room(long long target_room){
    if(room_map[target_room] == 0) {
        return target_room;
    } else {
        room_map[target_room] = get_allocated_room(room_map[target_room]);
        return room_map[target_room];
    }
}

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;
    for(int i=0;i<room_number.size();i++){
		long long allocated_room = get_allocated_room(room_number[i]);
 		answer.push_back(allocated_room);
		room_map[allocated_room] = allocated_room + 1;
    }
    return answer;
}

 

4. 느낀점

union-find를 잘 안 다뤄봐서 생각해내지 못했던 것 같다.

관련 문제들을 좀 더 풀어보자