[Programmers] 호텔 대실

프로그래머스

 

 

 

1. 구현 아이디어 1 - 틀렸습니다

백준 1931번 회의실 배정 문제나 저번에 포스팅한 과제 진행하기 문제와 비슷한 그리디 알고리즘 유형이다.

 

이전에 풀었던 기억을 되살려 아래에 적은 순서대로 풀었다.

1. 끝나는 시간을 기준으로 book_time을 정렬한다
2. 필요한 객실의 수를 관리하는 벡터 rooms를 만든다
3. book_time에 있는 원소(elem)들을 순회하며 rooms에 있는 원소(room=rooms[i])와 비교한다 (2중 반복문)
   3-1. 만약 elem의 시작하는 시간 >= room의 끝나는 시간 + 10분이면(= 같은 객실 사용 가능) rooms[i]를 갱신한다
   3-2. 사용할 수 있는 객실이 없으면 rooms에 원소를 추가
4. rooms 벡터의 원소의 개수가 정답이 된다

 

book_time의 길이가 최대 1,000이므로 2중 반복문을 돌아도 시간이 넉넉하다.

 

입출력 예 #1

rooms 벡터는 room1, room2, room3가 원소가 되도록 하고 각 room에서 가장 시간이 늦은 시간대(오른쪽에 있는)를 저장한다.

 

3-1번에서 시간을 비교를 할 때는 시간을 분 단위 int형 정수로 변환하여 비교하는 것이 쉽다! → 전체 코드의 compareTime 함수 참고

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool comp(vector<string> a, vector<string> b) {
    if (a[1] < b[1]) return true;
    
    if (a[1] == b[1]) return a[0] < b[0];
    
    return false;
}

// a에 10분을 추가한 시각보다 b가 더 뒤면 true 반환
bool compareTime(string a, string b) {
    int ah = stoi(a.substr(0, 2));
    int am = stoi(a.substr(3, 2));
    
    int bh = stoi(b.substr(0, 2));
    int bm = stoi(b.substr(3, 2));
    
    return (ah * 60 + am + 10) <= (bh * 60 + bm);
}

int solution(vector<vector<string>> book_time) {
    
    // 1. 끝나는 시간을 기준으로 정렬한다
    sort(book_time.begin(), book_time.end(), comp);
    
    // 2. Room 리스트를 만들어
    vector<vector<string>> rooms;
    
    // 3. book_time에 있는 원소(elem)들을 순회하며 rooms에 있는 원소(room)와 비교 ...
    for (auto elem : book_time) {
        // 처음에는 rooms가 비어있으니 무조건 객실 하나 추가
        if (rooms.empty()) {
            rooms.push_back(elem);
            continue;
        }
        
        bool useSameRoom = false;
        for (int i = 0; i < rooms.size(); i++) {
            vector<string> room = rooms[i];
            
            // 만약 elem의 끝나는 시간 + 10분 <= elem의 시작 시간 ...
            // (= 같은 객실을 사용할 수 있음)
            if (compareTime(room[1], elem[0])) {
                // room을 elem로 갱신
                rooms[i] = elem;
                useSameRoom = true;
                break;
            }
        }
        
        // 같은 객실 쓸 수 없으면 객실 하나 더 추가해야 함
        if (!useSameRoom) rooms.push_back(elem);
    }
    
    // Room의 원소의 개수가 답이 될 것!
    return rooms.size();
}

 

잘 풀었다고 생각했는데 대부분의 테케가 실패하였다 ㅠㅠ

질문 게시판의 반례 모음집을 통해 문제점을 발견할 수 있었다.

 

 

위의 코드에서는 들어갈 수 있는 객실이 여러 개일 때(= 3-1번을 충족하는 room이 여러 개일 때), 가장 최근의 room에 들어가게 된다.

이럴 경우는 가장 최근의 room이 아니라 끝나는 시간과 시작하는 시간 사이 갭이 최소인 room을 선택해야 한다.

 

2. 구현 아이디어 2 - 정답입니다!

그러면 들어갈 수 있는 객실이 여러 개일 때 ... 객실을 컨테이너(벡터나 우선순위 큐?)에 저장했다가 갭이 최소인 room을 선택해 ...? 라고 생각했지만 그러면 3중 반복문을 돌아야 하므로 ... 좋은 코드가 아니다 (그것도 레벨 2 문제인데 ...)

 

맨 처음에 끝나는 시각을 기준으로 정렬했는데, 시작하는 시각을 기준으로 정렬해보니 위에서 틀렸던 테스트 8이 통과하였다.

그래서 시작하는 시각을 기준으로 정렬하여 문제를 다시 풀어 해결할 수 있었다! (핵심 로직은 구현 아이디어 1과 동일하다)

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool comp(vector<string> a, vector<string> b) {
    if (a[0] < b[0]) return true;
    
    if (a[0] == b[0]) return a[1] < b[1];
    
    return false;
}

// a >= b + 10분일 경우 true 반환
bool compareTime(string a, string b) {
    int ah = stoi(a.substr(0, 2));
    int am = stoi(a.substr(3, 2));
    
    int bh = stoi(b.substr(0, 2));
    int bm = stoi(b.substr(3, 2));
    
    return (ah * 60 + am) >= (bh * 60 + bm + 10);
}

int solution(vector<vector<string>> book_time) {
    
    // 1. 시작하는 시간을 기준으로 정렬한다
    sort(book_time.begin(), book_time.end(), comp);
    
    // 2. Room 리스트를 만들어
    vector<vector<string>> rooms;
    
    // 3. book_time에 있는 원소(elem)들을 순회하며 rooms에 있는 원소(room)와 비교 ...
    for (auto elem : book_time) {
        // 처음에는 rooms가 비어있으니 무조건 객실 하나 추가
        if (rooms.empty()) {
            rooms.push_back(elem);
            continue;
        }
        
        bool useSameRoom = false;
        for (int i = 0; i < rooms.size(); i++) {
            vector<string> room = rooms[i];
            
            // 만약 elem의 시작하는 시간 >= room의 끝나는 시간 + 10분 ...
            // (= 같은 객실을 사용할 수 있음)
            if (compareTime(elem[0], room[1])) {
                // room을 elem로 갱신
                rooms[i] = elem;
                useSameRoom = true;
                break;
            }
        }
        
        // 같은 객실 쓸 수 없으면 객실 하나 더 추가해야 함
        if (!useSameRoom) rooms.push_back(elem);
    }
    
    // Room의 원소의 개수가 답이 될 것!
    return rooms.size();
}

 

이제 비슷한 유형이 나오면 시작하는 시각이나 끝나는 시각으로 정렬하고 문제를 푼다는 것은 익혔으나, 둘 중 어떤 것을 선택해야 하는지는 아직 확실하게 모르겠다 🫠

정진하자 !