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

[문제]

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

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

 

[풀이]

Union-Find 알고리즘을 사용해서 풀었다.

(Union-Find 알고리즘 : https://tnwlswkd.tistory.com/33 )

 

고객이 원하는 방이 아직 배정받지 않은 방이라면 해당 고객에게 배정해주고 map에 다음 칸의 방으로 초기화한다.

이미 배정받은 방이라면 Find 함수를 통해 해당 방을 기준으로 다음 방에서 비어있는 방을 찾아 배정해준다.

 

또한 배열이 아닌 맵을 사용한 이유는 k의 범위가 1 이상 10^12 이하이므로 배열을 사용하면  10^12 크기의 배열을 선언하여 메모리 부족이 발생하게 된다. 

 

 

항상 Union-Find 알고리즘 구현할 때, else 부분에서 초기화 해주는걸 깜박한다.

 

[코드]

 

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

using namespace std;

map <long long,long long > m;

long long Find(long long num)
{
    if(m[num]==0)
    {
        m[num]=num+1;
        return num;
    }
    else    return m[num]= Find(m[num]);
    
}

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 room= room_number[i];
        if(m[room] == 0)
        {
            answer.push_back(room);
            m[room]=room+1;
        }
        else
        {
            long long res = Find(room);
            answer.push_back(res);
        }
    }
    return answer;
}