[프로그래머스, C++] 호텔 방 배정

문제 링크

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

 

 

 

풀이

효율성 문제라길래 해설을 보았고 union-find 알고리즘으로 푸는 문제였다.

시간 복잡도는 O(nlogN)으로 풀어야 효율성 테스트 케이스가 풀린다고 한다.

 

// findRoom() --- 전역 변수로 map을 선언하는 대신 참조자로 매개변수로 받아서 구현하였다.

if(요구하는 방번호는 배정해도 된다)

    map에 요구하는 방 번호는 다음 방 번호 저장한다.(다음 방 번호를 재귀로 찾을 수 있도록)

    배정 안된 것의 번호를 리턴

 

else(이미 배정된 것이 있다)

    배정 안된 것의 번호를 찾아서 저장

    map에는 배정 안된 것의 다음 번호를 저장(나중에 또 물어보면 바로 찾을 수 있도록, 순차적으로X)

    배정 안된 것의 번호를 리턴

 

예시를 들자면,

문제에서 1, 2, 3, 4, 5, 6 방이 있을 때, 1, 3, 4, 1, 3, 1을 request 한다면,

1, 3, 4까지는 주다가

m[1] = 2;

m[3] = 4;

m[4] = 5;

그 다음은

a) 1을 찾을 경우, map[1]에는 2값이 들어 있고 map[2]에 3을 저장 후, 2를 리턴, map[1] = 3을 저장후 2를 리턴

b) 3을 찾을 경우, map[3]에는 4가 들어있고 map[4]에는 5가 들어있고, 5는 배정된 것이 없으니 map[5]에는 6을 저장 후 , 5를 리턴, map[4] = 6을 저장, map[3]에는 6을 저장 후, 5를 리턴

c) 1을 찾을 경우, map[1]에는 3이 저장돼있고 map[3]에는 6이 저장되고 6은 없으니 map[6]에 7을 저장 후 map[3]에도 7, map[1]에도 7을 저장후 6을 리턴

 

// 결론

방문하는 것은 모두 빈 방을 가리키도록 저장하여 속도를 절감시킨다.

 

#include <string>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

// 다음 번호로 매칭
// union - find 알고리즘

long long findRoom(long long& key, map<long long, long long>& m){
    if(m.find(key) == m.end()){
        // 배정된 것이 없다.
        m[key] = key+1;         // 배정된 것의 다음 방 번호를 저장
        return key;
    }
    else{
        // 이미 배정된 것이 있다
        long long noReserve = findRoom(m[key], m);      // 배정이 안된 것의 번호
        m[key] = noReserve+1;       // 배정이 안된 것의 번호 다음 방을 저장
        return noReserve;
    }
}

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;
    map<long long, long long> roomList;        // 배정될 맵
    
    // union-find
    for(int i=0; i<room_number.size(); i++){
        long long request = room_number[i];
        long long response = findRoom(request, roomList);
        answer.push_back(response);
    }
    // for(auto iter=roomList.begin(); iter!=roomList.end(); iter++)
    //     cout<<"("<<iter->first<<", "<<iter->second<<")"<<endl;
    return answer;
}