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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

문제를 처음 봤을 때 set으로 구현하면 될 것이라고 생각했다가 시간 초과가 발생하여 한참 해맸던 문제이다. long long사용해야하는데 습관적으로 int를 사용하여 시간을 많이 소비했다. 조심할 것.

풀이

map<long long, long long> m을 생성하여 key에 원하는 방 번호, value에 배정할 방 번호를 갱신하는 방식으로 구현하여 해결하였다.

1. map[원하는 방 번호] == 0인 경우(map[원하는 방 번호]에 아무 값도 없는 경우)에 원하는 방을 배정해주고 map에는 방 번호 + 1 씩 확인하여 빈 번호로 할당해준다.
2. map[원하는 방 번호] != 0 인 경우 원하는 방 번호가 이미 할당되었다는 의미이므로 1에서 갱신한map[원하는 방 번호]값을 배정해주고map에는 방 번호 + 1 씩 확인하여 빈 번호로 할당해준다.

코드

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

using namespace std;

map<long, long> m;

// 배정 가능한 번호를 찾는 함수
long long find(long long u){
    if(!m[u]) return u;
    return m[u] = find(m[u]);
}

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 cur = room_number[i];
        // 원하는 방 번호 배정이 가능할 때
        if(!m[cur]){
            answer.push_back(cur);
            m[cur] = find(cur+1);
        }else{
            long long tmp = find(cur);
            answer.push_back(tmp);
            m[tmp] = find(tmp + 1);
        }
    }
    return answer;
}