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

문제 링크: programmers.co.kr/learn/courses/30/lessons/64063

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

1. 주의할 점

- 범위가 1~10^12를 어떻게 처리할 것인가 → 배열 시도시 컴파일 에러

- Room_Number 벡터로 1이 20만개 들어온다고 할때, 하나하나 다음칸을 확인한다 → O(N^2): TLE

 

2. 구현

- 해당 방이 배정되었다면, 다음 방을 가리키도록 한다 → '유니온 파인드' 처럼 생각한다 → O(NlgN)

Ex. 순서대로 2,2,3이 들어오고 추가로 2가 들어온다면, 2,2,3은 모두 다음으로 비어있는 칸인 5를 가리키도록 하여 2가 5에 할당되도록 한다

- Map을 이용하여 10^12도 처리할 수 있도록 한다. Map에는 배정된 방의 숫자가 기록된다

- Find_P(x) 함수를 통하여 숫자 X가 Map에 없다면, 비어있는 방이므로 X를 반환한다. 비어있지 않다면, M[x] = find_p(it->second)를 통해 계속해서 부모를 갱신해준다

- Solution함수에서 Want가 원하는 방 번호지만, 실제로 들어갈 수 있는 방번호는 canGo에 저장된다

- canGo함수를 정답 벡터에 추가한 후, m[canGo]가 canGo바로 뒤인 canGo+1이 가리키는 빈방을 가리키도록 한다

#include <string>
#include <vector>
#include <map>
using namespace std;
map<long long, long long> m;
map<long long, long long> ::iterator it;

long long find_p(long long x){
    it = m.find(x);
    if(it==m.end())  return x;
    return m[x] = find_p(it->second);
}

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;
    for(long long i=0;i<room_number.size();i++){
        long long want = room_number[i];
        long long canGo = find_p(want);
        answer.push_back(canGo);
        m[canGo]=find_p(canGo+1);
    }
    return answer;
}