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

1.문제

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

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

 

2. 풀이

이 문제는 빈 방을 배정해 주었으면 그 방 현재 방 번호+1 또는 현재 방 번호+a 로 다음 빈 방번호를 가리키도록 갱신해주어야 한다.

이 방식을 어떻게 효율적으로하나 했더니 재귀함수를 이용해서 할 수 있었다.

즉, 재귀적으로 그 다음 빈 방 번호를 저장하는 것이다. (Union-find 방식)

 

그러면 O(nlogn)으로 해결 가능!

 

 

 

3. 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;

vector<long long> answer;
map<long, long> m;

long long find(long long num){
    if(m[num] == 0){
        answer.push_back(num);
        m[num] = num + 1;
        return num;
    }
    return m[num] = find(m[num]);
}

vector<long long> solution(long long k, vector<long long> room_number) {
    long long size = room_number.size();
    for(long long i=0; i<=size; i++){
        m[i] = 0;
    }

    for(long long i=0; i<size; i++){
        long long num = room_number[i];

        if(m[num] ==0){
            answer.push_back(num);
            m[num] = num+1;
        }
        else{
            find(m[num]);
        }
    }

    return answer;
}

---

참고 : hwan-shell.tistory.com/160