문제 푼 날짜 : 2021-06-08

문제

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

접근 및 풀이

< 문제에 주어진 알고리즘 >
1. 한 번에 한 명씩 신청한 순서대로 방을 배정합니다.
2. 고객은 투숙하기 원하는 방 번호를 제출합니다.
3. 고객이 원하는 방이 비어 있다면 즉시 배정합니다.
4. 고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.

문제를 읽어보면 이중 반복문을 이용해서 쉽게 풀릴 것 같다는 생각이 들었다.
실제로 이중 반복문으로 문제에 주어진 알고리즘을 따라 어렵지 않게 구현을 할 수 있었다.
하지만, 이 문제에는 효율성 테스트를 포함하고 있었다...
정확성 테스트는 충분히 통과할 수 있지만 효율성 테스트에서 시간 초과, 메모리 초과 난리가 났다.
효율성 테스트를 통과하기 위해 다른 방법을 생각해야 했다.
여러 시도를 했지만, 계속해서 같은 문제에서 시간 초과가 나서 kakao tech 풀이를 참고했다.(https://tech.kakao.com/2020/04/01/2019-internship-test/)

이 풀이에서 내가 생각한 핵심은 배정된 방을 최대한 탐색하지 않도록 하는 것이다.
반복문으로 방 하나하나씩 빈 방을 찾기 위해서 차례대로 탐색하는 것이 아니라, 이미 채워진 방들이 그 다음 방들중 가장 가까운 빈 방을 가리키게 해서 탐색시간을 줄이도록 하는 것이다.
이것을 구현하기 위해 C++ STL 중에 map을 이용하였다.
map에 key를 해당 방, value를 해당 방 다음에 있는 가장 가까운 빈 방으로 나타내었다.

코드

틀린 코드

#include <string>
#include <vector>

using namespace std;

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer(room_number.size());
    vector<bool> isUsed(k, false);
    
    for (int i = 0; i < room_number.size(); i++) {
        long long want = room_number[i];
        if (!isUsed[want - 1]) {
            isUsed[want - 1] = true;
            answer[i] = want;
        } else {
            while (true) {
                if (!isUsed[want - 1]) {
                    isUsed[want - 1] = true;
                    answer[i] = want;
                    break;
                }
                want++;
            }
        }
    }
    return answer;
}

통과 코드

#include <string>
#include <vector>
#include <map>

using namespace std;

map<long long, long long> rooms;

long long find(long long num) {
    if (rooms[num] == 0) return num; // 방이 비어있으면 바로 배정
    else return rooms[num] = find(rooms[num]); // 방이 비어있지 않으면 빈방을 찾으면서 각 방이 다음으로 가리키는 방 update
}

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 want = find(room_number[i]);
        answer.push_back(want);
        rooms[want] = want + 1; // 다음 방을 가리키도록 update
    }
    return answer;
}

결과

피드백

항상 풀이를 보고 풀면 허무하다. 이런 생각을 왜 못했을까 하는 자책이 너무 많이 든다.
여러 고수분들의 포스팅을 참고하면서 좀 더 열심히 공부를 해야겠다.