[1일 1알고] 호텔 방 배정

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

프로그래머스

 

방을 배정할 때 원하는 방이 이미 배정되어있다면 크면서도 가장 가까운 값을 가지는 방을 배정해줘야합니다.

 

일단 저는 처음에 연결리스트를 사용해서 빠르게 접근하는 방법을 생각했습니다. 

예를 들어 2를 방문했다면 1->3, 2->3과 같이 이어주려고 했습니다.

 

그런데 기본적으로 연결리스틀 만들기 위해서는 노드를 미리 만들 필요가 있지만 문제의 k는 최대 10^12이기 때문에 노드를 미리 만들 수 없습니다.

 

따라서 다른 방법을 생각해야했는데 이를 위해 union-find와 비슷하게 만들었습니다.

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

unordered_map<long long, long long> room_map;
long long Find(long long number)
{
    if (room_map.find(number) == room_map.end())
    {
        return number;
    }

    room_map[number] = Find(room_map[number]);
    return room_map[number];
}

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 number = room_number[i];

        long long assignedRoom = Find(number);

        answer.push_back(assignedRoom);

        room_map[assignedRoom] = Find(assignedRoom + 1);
    }

    return answer;
}

순서가 상관 없기 때문에 속도를 위해 unordered_map을 사용했습니다.

 

현재 사람이 원하는 방을 배정받고, 같은 방을 원하면 돌려줄 방을 다시 찾아 할당합니다.