2019 카카오 겨울 인턴십 호텔 방 배정(C++)

몇개 시간초과 뜸

 

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

using namespace std;

map<long long,long long>room; 

long long find(long long node){
    if(room[node]==0)return node;
        
    return room[node]=find(room[node]); 
}

long long unions(long long x){
    long long xp=find(x);
    
    room[xp]=xp+1;
    return xp;
}

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 num=unions(room_number[i]);
        answer.push_back(num);
    }
    
    
    
    return answer;
}

 

unions 함수를 지우고 find 다음 바로 room[num]=num+1 하니까 통과

함수 호출이 그렇게 걸림돌이 되나.. -> map 사용의 문제였다. map하면 시간초과 뜬다. unordered_map이 더 빠르다.

#include <string>
#include <vector>
#include<unordered_map>

using namespace std;

unordered_map<long long,long long>room; 

long long find(long long node){
    if(room[node]==0)return node;
    return room[node]=find(room[node]); 
}

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 num=find(room_number[i]);
        answer.push_back(num);
        room[num]=num+1;
    }
    
    return answer;
}