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

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

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

<풀이>

1. 고객이 원하는 방 정보를 입력받는다.

2. 규칙에 따라 방을 배정하고, 배정된 방을 반환한다.

 

<해법>

1. "효율성 테스트"가 있는 문제의 마음가짐

=> 단순히 구현을 요구하는 문제가 아님을 깨달아야 합니다. 문제를 읽으면서, 어떤 알고리즘 또는 자료구조를 사용할지 생각해야합니다. 저는 어떤 방에 대한 다음 방의 정보를 저장하는 방법을 생각했고, 이 때 map자료구조를 사용하였습니다.

 

#include <iostream>
#include <string>
#include <vector>
#include <map>
 
using namespace std;
 
//Key: 방 번호, Value: 다음방 번호
map<long long, long long> m;
 
//어떤 방의 다음 방을 갱신하는 함수
long long findNextRoom(long long roomNum) {
    if (m[roomNum] == 0) {
        return roomNum;
    }
 
    return m[roomNum] = findNextRoom(m[roomNum]);
}
 
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++) {
 
        if (m[room_number[i]] == 0) {
            answer.push_back(room_number[i]);
            m[room_number[i]] = findNextRoom(room_number[i] + 1);
        }
        else {
            long long foundRoom = findNextRoom(room_number[i]);
            answer.push_back(foundRoom);
            m[foundRoom] = findNextRoom(foundRoom + 1);
        }
    }
 
    //결과 반환
    return answer;
}

 

문제해결능력에 대해 알아볼 수 있는 문제였습니다.