[C++/PGS] Lv.4 : 호텔 방 배정 (재귀)

 

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

프로그래머스

---

프로그래머스 레벨 4. 정답률 35%

재귀 사용 문제!!

 

1. 효율성 실패 (78.8/100)

테스트케이스는 다 맞았는데, 효용성은 0점 ㅋㅋ

아마도 아래 부분이 문제였을 것이다.

 

while(rooms.find(n) != rooms.end()){
    n++;
}

 

빈 방을 찾을때까지 while문을 돌렸는데, 이 부분을 최적화해야 통과할 것 같다.

다음 빈 방을 효율적으로 저장할 수 있는 방법이 뭐가 있을까

고민해봐도 모르겠어서 질문 게시판에서 힌트를 얻었다 >> 재귀적으로 빈 방을 찾아주면 된다고 함!

 

2. 성공 코드

 

우선, 방 번호와 고객을 저장하는 게 아니라, 방 번호와 그 다음 빈 방 번호를 세트로 저장해야 한다. (포인터 역할)

그리고 현재 방이 비어있을 때는 해당 방을 배정 후 + 다음 방에 포인터 연결.

현재 방에는 사람이 있고 현재 방과 연결된 포인터(다음 방)이 비어있을 경우, 그 방을 리턴 후, 그 다음 방에 포인터 연결

이런 식으로 재귀적인 탐색을 거쳐주어야 한다.

 

후 어렵다....

 

참고로, cpp의 경우 반드시 unordered_map을 사용해야 시간초과 없이 통과할 수 있다!

 

 

 

나의 풀이

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

unordered_map<long long, long long> rooms; // k: 방 번호, v: 다음 빈 방 번호

long long findRoom(long long roomNumber){
    if(rooms.find(roomNumber)==rooms.end()) { // 빈 방일 때
        return roomNumber;
    }
    // 빈 방이 아니라면, 그 다음 방을 탐색
    return rooms[roomNumber] = findRoom(rooms[roomNumber]);
}

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 room = findRoom(room_number[i]);
        answer.push_back(room);
        rooms[room] = room+1;
    }
    return answer;
}