[프로그래머스] Level 4. 호텔 방 배정

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

프로그래머스

 

 

처음엔 배열로 parent를 구현했는데, 시간초과가 발생했다. unordered_map을 사용하니 통과함.

방이 찼을 경우, 자기다음으로 큰 방번호를 parent에 넣는다.

방번호를 찾을때, parent를 올바른값으로 갱신하는 부분도 들어가있다.

for(long long i:prevs) parent[i] = room;

 

 

전체코드

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

long long getRoom(unordered_map<long long ,long long >& parent, long long room){
   vector<long long> prevs;
    while(true){
        if(!parent.count(room)) break;
        
        prevs.push_back(room);
        room = parent[room];
    }
    
    for(long long i:prevs) parent[i] = room;
    return  room;
}

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;
    
    unordered_map<long long,long long> parent;
    for(int i=0; i<room_number.size(); i++){
        long long room = getRoom(parent, room_number[i]);
        answer.push_back(room);
        parent[room] = room+1;
    }
    
    return answer;
}