2019 Winter Kakao Internship - Hotel room

 

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

프로그래머스

First trial code :

#include <string>
#include <vector>
using namespace std;

long long find(long long room, vector<long long>& selected) {
    if (room == selected[room]) return room;
    else {
    	// Update the last empty room resursively
        selected[room] = find(selected[room], selected);
        return selected[room];
    }
}

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer(room_number.size());
    vector<long long> selected(k+1LL);

    long long targetRoom = 0;
    long long nextRoom = 0;
    long long i = 0;

	//Initiate 'selected' array to indicate the assignment
    for (i = 0; i <= k; i++) selected[i]=i;

    for (i = 0; i < room_number.size(); i++) {
        targetRoom = find(room_number[i], selected);
        answer[i] = targetRoom;
        nextRoom = 0LL;
        
        if (targetRoom + 1LL <= k) {
            nextRoom = find(targetRoom + 1LL, selected);
        }
        selected[targetRoom] = nextRoom;
    }
    return answer;
}

But this code has been failed with 'memory excess'

 

Why it has failure with big memory usage ? 'find' function will have too many resursion ?

It's because 'selected' vector should be allocated for very big number.  (1 <= k <= 10^12)

So, only to allocate required rooms, 'map' will be good choice to use.

 

#include <string>
#include <vector>
#include <map>
using namespace std;

long long find(long long room, map<long long, long long>& selected) {
    map<long long, long long>::iterator it;
    long long lastRoom;
    
    it = selected.find(room);
    
    // If the room is no in the map, that's the last one
    if ( it == selected.end() ) return room;
    else {
        // If the room is in the map, check next room
        lastRoom = find(it->second , selected );
        // update every room's next to last one
        it->second = lastRoom;
        return lastRoom;
    }
}

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer(room_number.size());
    map<long long, long long > selected;

    long long targetRoom = 0;
    long long i = 0;

    for (i = 0; i < room_number.size(); i++) {
        targetRoom = find(room_number[i], selected);
        selected.insert(make_pair(targetRoom, targetRoom+1LL));
        answer[i] = targetRoom;        
    }
    return answer;
}

 

We can try this problem using 'union find' method also.