programmers 호텔 방 배정

programmers 호텔 방 배정 : programmers.co.kr/learn/courses/30/lessons/64063

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

2019 카카오 개발자 겨울 인턴십, level4의 호텔 방 배정 문제입니다.

 

처음에는 set을 이용해서 방이 비어있는지 확인하고 없으면 +1씩 체크하는 방식으로 코딩하였습니다.

결과는 역시 정확도만 만점이고 효율성에서 나락되었습니다.

이걸 어떻게 해야할지 오래 고민해보았는데, 

+1씩 확인해야 하는 탐색과정을 줄이는게 가장 중요할 것 같았습니다.

 

그래서 만약 현재 사람이 원하는 방이 비어있다면

'그 방에 배정시키고,

만약 이 방을 다른 사람이 또 원하게 된다면 현재방의 +1 방에 바로 배정시키자' 로 접근했습니다.

 

여기서 중요한 것은 현재방의 +1 방이 또 배정되어있는 상태인가? 입니다.

결국 현재 배정한 방의 그 다음방이 '어디까지 배정되어 있는지'를 알아야 합니다.

+1씩 탐색하는 것은 첫 코딩때 set을 이용한 것과 같지만, 이를 계산해서 미리 알아둔다면

그 다음에는 또 같은 방에 대해서는 +1씩 탐색할 필요가 없으니 탐색시간을 줄일 수 있습니다.

map을 통해서 <현재 배정한 방, 그 다음방의 연결된 마지막 방> 의 형식으로 문제를 해결하였습니다.

 

#include <string>
#include <vector>
#include <map>
using namespace std;
using ll = long long;

map<ll, ll> visit;

ll findNextRoom(ll room){
    if(visit[room] == 0) return room; // 배정되어 있지 않은 room 방에 배정시킬 수 있습니다
    visit[room] = findNextRoom(visit[room]); // room 방이 어디까지 연결되어 있는지 탐색하는 동시에 연결시킵니다
    return visit[room];
}

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;
    
    for(auto room : room_number){
        if(visit[room] == 0){ // 배정되어있지 않다면
            answer.push_back(room); // 배정시키고
            visit[room] = findNextRoom(room+1); // +1 방이 어디까지 연결되어있는지 탐색합니다
        }
        else{ // 배정되어있다면
            ll nextRoom = findNextRoom(room+1); // +1 방이 어디까지 연결되어있는지 탐색합니다
            answer.push_back(nextRoom); // 찾아낸 방에 배정합니다
            visit[nextRoom] = findNextRoom(nextRoom+1); // 찾아낸 방의 +1 방이 어디까지 연결되어 있는지 탐색합니다
        }
    }
    
    return answer;
}