2019 카카오 개발자 겨울 인턴십 호텔 방 배정 ( C++ )

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

프로그래머스

 

 

먼저 깔끔한 문제풀이 설명은 카카오 테크 블로그에서 볼 수 있다.

https://tech.kakao.com/2020/04/01/2019-internship-test/

2019 카카오 개발자 겨울 인턴십 코딩 테스트 문제 해설

 

 

효율성 테스트가 있는 문제로 k의 범위가 크기 때문에 방을 하나하나 순차적으로 검사해주면 효율성 테스트에 실패한다.

효율성을 통과하는 방법은 위의 카카오 테크 블로그에 그림과 함께 굉장히 잘 설명되어있는데, 

요청한 방이 빈방이라면 바로 배정하고 배정된 방이 바로 다음 방을 가리키도록 해준다.

요청한 방이 빈방이 아니라면 그 방이 가리키는 다음 방을 계속 찾아가며 빈방을 찾는다.

이 방법은 Union-Find 알고리즘을 사용해서 효율적으로 구현할 수 있다. 부모 노드가 다음 빈 방의 번호 값을 가지도록 해주면 된다.

 

#include <string>
#include <vector>
#include <map>
using namespace std;
 
map<long long, long long> m;
 
long long getNextEmptyRoom(long long num) {
    if (m[num] == 0) return num;
    return m[num] = getNextEmptyRoom(m[num]);
}
 
 
vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;
 
    for (long long num : room_number) {
        long long emptyRoom = getNextEmptyRoom(num);
        answer.push_back(emptyRoom);
        m[emptyRoom] = emptyRoom + 1;
    }
 
    return answer;
}