[Softeer][데브크루 2일차] 소프티어 Lv.2 회의실 예약 (21년 재직자 대회 예선)

https://softeer.ai/practice/6266

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

문제 설명

회의실의 수 n 예약된 회의의 수 m

이후 n개의 줄에 회의실의 이름 r이 주어짐

이어 M개의 줄에 각 회의가 배정된 회의실의 이름 r과 시작 시각 s, 그리고 종료 시각 t가 주어짐

3 7
grandeur
avante
sonata
sonata 14 16
grandeur 11 12
avante 15 18
sonata 10 11
avante 9 12
grandeur 16 18
avante 12 15

 

각 회의실에 대한 가능한(회의가 없는) 시간대를 회의실 이름의 오름차순으로 출력하면 됨

Room avante:
Not available
-----
Room grandeur:
2 available:
09-11
12-16
-----
Room sonata:
3 available:
09-10
11-14
16-18

 

 

풀이

입출력이 일단 굉장히 복잡하고 깐깐하다.

 

시간대별 회의실의 상태를 status 벡터로 관리했다

status[i][j] = i번 회의실의 j시간에 가능 여부

 

이 과정에서 회의실 이름과 회의실 번호를 매칭시키기 위해 자료구조 map을 사용했다

map<회의실 이름(키), 회의실 번호(값)> status

이때 회의실 이름 영문 오름차순으로 해야하는 출력 조건을 자동으로 할 수 있다는건 덤

(맵 자료구조는 키를 오름차순으로 저장한다)

    // 회의실에 번호 부여
    map<string, int> room;
    string r;
    for(int i=0; i<n; i++) {
        cin >> r;
        room.insert({r, i});
    }

 

코드

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int,int> ci;

// 9시부터 18시까지 시간대 갯수
const int TIME = 9; 
const int START = 9;
const int END = 18;

int main() {
    int n, m;
    cin >> n >> m;

    // 회의실에 번호 부여
    map<string, int> room;
    string r;
    for(int i=0; i<n; i++) {
        cin >> r;
        room.insert({r, i});
    }

    // 각 회의실 예약내역 추가
    vector<vector<ci>> reserve(n, vector<ci>());
    int s, t;
    for(int i=0; i<m; i++) {
        cin >> r >> s >> t;
        int room_num = room[r];
        reserve[room_num].push_back({s,t});
    }

    int cnt = 0;
    for(auto iter=room.begin(); iter!=room.end(); iter++) {
        // 가능한 시간대 구하기
        int room_num = room[iter->first];
        vector<ci> unavailable = reserve[room_num];
        sort(unavailable.begin(), unavailable.end());
        vector<ci> available;
        
        int cur = START;
        for(ci i : unavailable) {
            if(i.first != cur) {
                available.push_back({cur, i.first});
            }
            cur = i.second;
        }
        if(cur != END) {
            available.push_back({cur, END});
        }

        // 출력하기
        cout << "Room " << iter->first << ":\n";
        if(available.size() > 0) {
            cout << available.size() << " available:\n";
            for(ci i : available) {
                if(i.first<10) cout << "0";
                cout << i.first << "-" << i.second << "\n";
            }
        } else {
            cout << "Not available\n";
        }
    
        cnt++;
        if(cnt != n) {
            cout << "-----\n";
        }
    }

    return 0;
}

 

 

시행착오

이제 m개 줄을 돌며 회의실 예약을 표시한다

avante 15 18 이 주어졌다면 

map[avante]를 통해 avante회의실의 번호 0을 뽑아내고

status[0][6] 부터 status[0][9] 까지를 false 로 채우는 형식

15부터 18이 아닌 6부터 9인 이유는 회의실 가능 최초 시간인 9를 각각 빼줬음

    // 회의실 상태 업데이트
    vector<vector<bool>> status(n, vector<bool>(TIME, true));
    int s, t;
    for(int i=0; i<m; i++) {
        cin >> r >> s >> t;
        int room_num = room[r];
        for(int i=s; i<t; i++) {
            status[room_num][i-START] = false;
        }
    }

 

 

이제 가능한 시간대를 구해야한다.

status 맵을 순회하면서 가능한 시간대를 구하고 바로 출력해주자.

 

시간대별 가능 여부가 벡터로 주어졌을 때 가능한 시간대는 어떻게 구할까?

 

각 회의실에 해당하는 status의 시간대별 가능 여부를 확인하면서

(1)가능했다가 불가능해지는 시점

(2)불가능했다가 가능해지는 시점

이 두가지를 branch 벡터에 저장한다.

// 가능한 시간대 구하기
    int cnt = 0;
    for(auto iter=room.begin(); iter!=room.end(); iter++) {
        int room_num = room[iter->first];
        
        vector<int> branch; // 가능과 불가능 경계 시간대 넣기
        bool tmp = true;
        for(int j=0; j<TIME; j++) {
            if(status[room_num][j] == tmp) {
                tmp = !tmp;
                branch.push_back(j+START);
            }
        }

 

status 벡터가 다음과 같다고 가정한다면,

시간대	1	2	3	4	5	6	7
가능여부	o	x	x	o	o	x	o

 

예시에서는 1 2 4 6 7 이 저장될거다

 

그럼 이를 해석하면 결국 가능한 시간대가

1-2, 4-6, 7-끝까지

이렇게 세가지라는 걸 알 수 있다

 

즉, branch 벡터에 있는 값을 차례대로 출력만 해주면 된다!

branch의 크기 / 2 는 가능한 시간대의 수와 같기 때문에

Available: branch.size()/2 로 가능하다.

 

참고로 출력 조건에 있는 "-----" 이거는 맨 마지막 방 밑에는 없다는 점 주의하자

(이걸 위해 마지막 방인 경우 -----를 출력 안하도록 cnt 변수를 넣었다)

// 출력
        cout << "Room " << iter->first <<":\n";
        if(branch.size() == 0) {
            cout << "Not available\n";
        } else {
            cout << branch.size()/2 + branch.size()%2 << " available:\n";
            for(int j=0; j<branch.size(); j+=2) {
                cout << timeString(branch[j]) << "-" << timeString(branch[j+1]) << "\n";
            }
        }

        cnt++;
        if(cnt != n) {
            cout << "-----\n";
        }

 

 

참고로 출력할 때 숫자 9는 09로 표시해야하고

만약 마지막 시간까지 사용 가능해서 branch 갯수가 홀수인 경우

마지막 줄의 두번째 수(branch[j+1])가 접근이 안되어서 0이 나온다.

이 예외 케이스를 처리하기 위해 timeString 함수를 임의로 만들어서 상단에 정의했다

// 9시부터 18시까지 시간대 갯수
const int TIME = 9; 
const int START = 9;
const int END = 18;

string timeString(int a) {
    if(a==0) return to_string(END);
    if(a<10) return "0"+ to_string(a);
    return to_string(a);
}

 

 

코드

#include <iostream>
#include <vector>
#include <map>

using namespace std;

// 9시부터 18시까지 시간대 갯수
const int TIME = 9; 
const int START = 9;
const int END = 18;

string timeString(int a) {
    if(a==0) return to_string(END);
    if(a<10) return "0"+ to_string(a);
    return to_string(a);
}

int main() {
    int n, m;
    cin >> n >> m;

    // 회의실에 번호 부여
    map<string, int> room;
    string r;
    for(int i=0; i<n; i++) {
        cin >> r;
        room.insert({r, i});
    }

    // 회의실 상태 업데이트
    vector<vector<bool>> status(n, vector<bool>(TIME, true));
    int s, t;
    for(int i=0; i<m; i++) {
        cin >> r >> s >> t;
        int room_num = room[r];
        for(int i=s; i<t; i++) {
            status[room_num][i-START] = false;
        }
    }

    // 가능한 시간대 구하기
    int cnt = 0;
    for(auto iter=room.begin(); iter!=room.end(); iter++) {
        int room_num = room[iter->first];
        
        vector<int> branch; // 가능과 불가능 경계 시간대 넣기
        bool tmp = true;
        for(int j=0; j<TIME; j++) {
            if(status[room_num][j] == tmp) {
                tmp = !tmp;
                branch.push_back(j+START);
            }
        }

        // 출력
        cout << "Room " << iter->first <<":\n";
        if(branch.size() == 0) {
            cout << "Not available\n";
        } else {
            cout << branch.size()/2 + branch.size()%2 << " available:\n";
            for(int j=0; j<branch.size(); j+=2) {
                cout << timeString(branch[j]) << "-" << timeString(branch[j+1]) << "\n";
            }
        }

        cnt++;
        if(cnt != n) {
            cout << "-----\n";
        }
    }

    return 0;
}