[2019 kakao winter internship] 04. 호텔 방 배정 (cpp/python)

호텔 방 배정

프로그래머스

문제 설명

<unordered_map>을 이용하여 주어진 호텔 방 번호를 맵의 key 값으로 생각하여 방 배정을 하고 다음 방 번호를 value 로 받아 방을 배정 받을때마다 다음 방 번호를 갱신하여 준다.

자료구조 trie 에서 착안하였다.

문제 풀이

소스코드 : C++

1. 손님이 원하는 방 번호가 담겨있는 room_number 를 key 로 받고 해당 key 가 없으면 unordered_map<LL,PLL> m에 insert({배정 받은 방번호, {배정 받은 손님 , 다음 방 번호}})해준다. 이 때 다음 방 번호는 배정 받은 방 번호 (key) +1 이다.
2. 만약 key 값이 이미 m에 있다면 value 값을 이용하여 다음 방 번호가 이미 배정 받았는지 확인하는 find_room 함수를 호출한다.
3. 해당 손님의 인덱스인 i와 다음 방 번호를 key 값을 인자로 넘겨 해당 key 가 존재하는지 확인한다.
4. 없다면 해당 key 를 insert 해주고 다음 key 값을 반환해준다.
   예를들어 1, 2, 3 번 방 모두 배정 받은 상태이고, 1번 방을 원하는 손님을 탐색할 때 해당 1,2,3번 방 모두 다음 방 번호를 4번을 value 로 갖기 위해 5 = m[4] = m[3] = m[2] = m[1] 이런식으로 재귀함수를 탈출하면서 갱신해준다.
5. 모든 손님의 방 배정이 끝나면 해당 방 번호와 손님의 인덱스를 vector<PLL> tmp에 담아 손님 인덱스 순으로 정렬한 후 answer에 push해준다.

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
#define PLL pair<long long,long long>
#define ll long long
#define endl '\n'

using namespace std;

unordered_map<ll, PLL> m;     //배정 받은 방번호, {배정 받은 사람, 다음 방 번호}
ll find_room(ll i, ll key){
    if(m.find(key)==m.end()){
        m.insert({key,{i,key+1}});
        return key+1;
    }
    else{ 
        ll nk = find_room(i, m[key].second);
        m[key].second = nk;
        return nk;
    }
}
vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;

    for(ll i=0; i<room_number.size(); i++){
        ll key = room_number[i];
        if(m.find(key)==m.end()){
            m.insert({key,{i,key+1}});
        }
        else{
            m[key].second = find_room(i,m[key].second);
        }
    }
    vector<PLL> tmp;
    for(auto res : m){
        tmp.push_back({res.second.first, res.first});
    }
    sort(tmp.begin(), tmp.end());
    for(auto ans : tmp)
        answer.push_back(ans.second);    
    return answer;
}
int main(){
    ll k;
    vector<ll> rn;

    k=10;
    rn = {1,3,4,1,3,1};

    for(auto ans : solution(k,rn))
        cout<<ans<<endl;

    return 0;
} 

여기서 쓸모 없는 계산이 한 번 더 일어났다. 이미 탐색 자체를 손님 순서대로 하기 때문에 새로운 vector<PLL> tmp 에 받아 다시 정렬하여 출력을 할 필요가 없는 것이다. 그리고 m에 손님의 인덱스도 받을 필요가 없어지므로 아래 코드와 같이 수정할 수 있다.

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
#define PLL pair<long long,long long>
#define ll long long
#define endl '\n'


using namespace std;
vector<long long> answer;
unordered_map<ll, ll> m;    
ll find_room(ll key){
    if(m.find(key)==m.end()){
        m.insert({key, key+1});
        answer.push_back(key);
        return key+1;
    }
    else{ 
        ll nk = find_room(m[key]);
        m[key] = nk;
        return nk;
    }
}
vector<long long> solution(long long k, vector<long long> room_number) {
    for(ll i=0; i<room_number.size(); i++){
        ll key = room_number[i];
        if(m.find(key)==m.end()){
            m.insert({key,key+1});
            answer.push_back(key);
        }
        else{
            m[key] = find_room(m[key]);
        }
    }
    return answer;
}

작은차이지만 효율성 면에서 차이를 보인다.

v01  

첫 번째 코드

두 번째 코드

소스코드 : Python

위 cpp로 푼 풀이와 큰 차이는 없다. 다만 파이썬은 재귀함수의 최대 호출 수가 1000 으로 재한되어있다. 이를 풀기위해

import sys
sys.setrecursionlimit(100000)

을 이용하여 재한을 1000 -> 100000으로 바꾸어 주었다.

이런것을 보면 파이썬은 재귀함수를 지양하는게 좀 더 좋을 것 같다는 생각이든다. 평소 복잡한 문제를 풀때는 반복문보다 재귀함수를 선호하는 편인데 역시 둘 다 할줄알아야하는 것 같다.

반복문과 재귀함수의 차이가 궁금하다면 -> 클릭

import sys
sys.setrecursionlimit(100000)

answer = []
m = {}  # idx번째 고객의 방 번호, 다음 방 번호

def find(i,key):
    global answer
    global m
    if key not in m:
        m[key] = key +1
        answer.append(key)
        return m[key]
    else:
        nk = find(i,m[key])
        m[key] = nk
        return nk

def solution(k, room_number):
    global answer
    global m
    for i in range(len(room_number)):
        key = room_number[i]    # 고객이 원하는 방 번호
        if key not in m:
            m[key] = key+1
            answer.append(key)
        else:
            m[key] = find(i,m[key])      

    return answer

input_k = 10
input_room_number = [1,3,4,1,3,1]

print(solution(input_k, input_room_number))