[개쉬운 풀이] 백준 19583 싸이버개강총회

https://www.acmicpc.net/problem/19583

문제

보영이는 알고리즘 동아리 HI-ARC를 운영하고 있다.

보영이와 운영진 일동은 20년도에 입학하는 신입생들을 맞이하기 위해 열심히 준비를 해왔으나, 전염병의 유행이 악화된 나머지 정부에서는 “사회적 거리두기”를 선언했고 그에 따라 학교에서는 교내 모든 동아리에 오프라인 모임을 자제하라는 공지를 하기에 이르렀다. 오프라인에서 모임을 자제하라는 권고가 나온 어려운 상황에도 불구하고, 보영이는 기지를 발휘하여 개강총회를 미튜브 스트리밍으로 대체하는 결정을 하게 된다.

하지만, 미튜브 스트리밍으로 개강총회를 하게 될 경우, 아래와 같은 문제가 있었다.

누가 개강총회에 왔는지 알 수 없다.
누가 개강총회 자리에 끝까지 남아있었는지 알 수 없다.
어떤 사람이 개강총회 스트리밍을 단순히 틀어놓기만 했는지 알 수 없다.
이런 문제를 해결하기 위해서, 다음과 같이 출석부를 관리하기로 결심했다.

개강총회를 시작하기 전에, 학회원의 입장 확인 여부를 확인한다. 학회원의 입장 여부는 개강총회가 시작한 시간 이전에 대화를 한 적이 있는 학회원의 닉네임을 보고 체크한다. 개강총회를 시작하자마자 채팅 기록을 남긴 학회원도 제 시간에 입장이 확인된 것으로 간주한다.
개강총회를 끝내고 나서, 스트리밍을 끝낼 때까지 학회원의 퇴장 확인 여부를 확인한다. 학회원의 퇴장 여부는 개강총회가 끝나고 스트리밍이 끝날 때까지 대화를 한 적이 있는 학회원의 닉네임을 보고 체크한다. 개강총회가 끝나자마자 채팅 기록을 남겼거나, 개강총회 스트리밍이 끝나자마자 채팅 기록을 남긴 학회원도 제 시간에 퇴장이 확인된 것으로 간주한다.
단, 00:00부터는 개강총회를 시작하기 전의 대기 시간이며, 개강총회 스트리밍 끝난 시간 이후로 남겨져 있는 채팅 기록은 다른 스트리밍 영상의 채팅 기록으로 간주한다.

이 때, 입장부터 퇴장까지 모두 확인된 학회원은 전부 몇 명인가?

생각

1. String name을 키로 Container를 구성해야하기 때문에 Vector 보다는 Map이나 SET을 사용하는 것이 빠르다.
2. Vector의 find는 O(N)이고, SET의 find는 O(logN)으로 SET이 더욱 빠르다.
3. string을 처리하는 것이 조금 귀찮고 시계열 데이터를 비교하기 편한 10진수로 나타내는 것이 좋다고 생각했다.
4. 입력 체팅 수에 대한 제한을 주지 않아서 당황했다.

-> while(cin >> time >> name)으로 해결

풀이

1. Container SET을 이용하여 시작시간 전 체팅들은 INSERT 한다.
2. 시계열 데이터들은 10진수로 변환한다.
3. 종료시간부터 스트리밍 종료시간까지 채팅들을 통해 SET에 포함되어있는지 확인한다.
4. 포함되어있으면 count하고 값들을 삭제한다. -> 이중 count 방지

#include <iostream>
#include <string>
#include <set>
using namespace std;

string S, E, Q;
set<string> arr;
set<string>::iterator iter;
int answer = 0;


void input(){
    cin >> S >> E >> Q;
}

//시계열 데이터를 10진수로 바꾸기
int timeToDec(string time){
    int hour, minutes;
    hour = (time[0] - '0') * 10 + (time[1] - '0');
    minutes = (time[3] - '0') * 10 + (time[4] - '0');
    int result = hour*60 + minutes;

    return result;
}

//출석부에 존재하는 가
bool isExisted(string name){
    // iter 사용법을 배워놓자.
    iter = arr.find(name);
    if(iter == arr.end()) return false; //존재하지 않으면 iter = arr.end()를 반환한다

    return true;
}

void inputValue(string name){
    if(!isExisted(name)){
        arr.insert(name);
    }
}

void process(string time, string name){
    //비교하기 쉽게 10진수로 변환한다.
    int startTime = timeToDec(S); // 개강총회를 시작한 시간 S
    int endTime = timeToDec(E);    // 개강총회를 끝낸 시간 E
    int streamingTime = timeToDec(Q); // 개강총회 스트리밍을 끝낸 시간 Q
    int realTime = timeToDec(time); // 체팅 시간

    // case 1 : 개강총회를 시작하기 전에
    if(realTime <= startTime){
        // 출석부에 기입
        inputValue(name);
    }

    // case 2 : 개강총회 끝나고 스트리밍 종료 사이
    else{
        if(endTime <= realTime && realTime <= streamingTime){
            //출석을 했다면 중복 count하지 않도록 지워주고,
            //answer에 +1 해준다.
            if(isExisted(name)) {
                arr.erase(iter);
                answer++;
            }
        }
    }
}

void sol(){
    string time, name;
    //입력값 제한을 주지 않아서 while문을 통해 해결하였다.
    while(cin >> time >> name){
         //문제를 풀면서 디버깅 하기 위함의 break 문
        if(time == "end") break;
        process(time, name);
    }

    cout << answer << endl;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    input();
    sol();

    return 0;
}

얻은 점

1. 은 find가 0(logN)이다.
2. 시계열 데이터는 10진수로 바꾸어서 처리하는 것이 편하다.
3. SET find()함 수는 iterator를 반환하므로 iter를 선언하는 법을 배우자.

-> set::iterator iter;
4. 은 hash_map으로 find 가 O(1)의 속도를 갖는다. 이를 활용하면 더 빠른 속도로 해결할 수 있을 것 같다.