[프로그래머스 lv3] 추석 트래픽 풀이

해설

요청 종료 시간과 수행시간이 여러 개 주어질 때, 1초당 최대 처리량을 구하는 문제이다.

 

1) 문자열을 순회하면서 파싱하고, 요청 시작시간과 요청 종료시간을 구해 각각을 다른 벡터에 넣어준다.

 

문자열을 파싱할 때는 sscanf 함수를 사용하면 포맷에 따른 정보를 바로 가져올 수 있다. hh, mm, ss, sss, t1(T의 소수점 앞부분), t2(T의 소수점 뒷부분)을 파싱 하고, 종료 시간을 정수형 시간으로 바꾼 뒤 시작 시간을 구해보자. 

 

T의 소수점 앞부분 t1에 대하여, 시작시간을 만들려면 종료시간에서 t1*1000-t1을 빼주어야 한다. t1*1000이 아닌 t1*1000-t1인 이유는, 처리시간에 시작과 끝을 포함한다고 주어졌기 때문이다. 예를 들어, 종료 시간이 7000이고 2초 동안 실행되었다면 시작시간은 5000이 아닌 5002이다. 5002 -> 6001 -> 7000 이렇게 2초 동안 수행된 것이기 때문이다. 

 

T의 소수점 뒷부분 t2에 대하여, 시작시간을 만들려면 종료시간에서 t2-1을 뺴주어야 한다. t2가 아닌 t2-1인 이유는 앞서 언급한 것과 마찬가지로 처리시간이 시작시간을 포함하기 때문이다.

 

요청 시작 시간들을 벡터 vst, 요청 종료 시간들을 ven에 넣고 각 배열을 정렬해놓자.

 

 

2) 구간의 시작 포인트를 st, 끝 포인트를 en이라고 할 때, 간격이 1초인 구간을 오른쪽으로 이동하면서 새로운 요청을 추가하고 구간을 벗어난 요청을 삭제하자.

 

구간이 0.001초 오른쪽으로 이동했을 때(st++, en++), 구간에 새로 들어오는 요청은 시작 시간이 en보다 작거나 같은 요청들이다. 따라서, vst 벡터를 이동하면서 시작 시간이 en보다 작거나 같은 녀석들을 지나고, 구간에 들어있는 요청의 개수(cnt)를 1 증가시켜준다.

 

구간에서 벗어나는 요청은 종료시간이 st보다 작은 요청들이다. 따라서, ven 벡터를 이동하면서 종료 시간이 st보다 작은 녀석들을 지나고, 구간에 들어있는 요청의 개수(cnt)를 1 감소시킨다.

 

우리는 특정 1초 구간에 들어있는 최대 요청 개수를 구해야 하므로 구간을 오른쪽으로 1초만큼 이동할 때마다 최대 cnt를 기록해놓는다.

모든 구간을 탐색한 뒤, cnt의 max 값을 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int y, m, d, hh, mm, ss, sss, t1, t2;
vector<int> vst, ven;

void parse(const vector<string>& lines) {
    
    for (auto x : lines) {

        sscanf(x.c_str(), "%d-%d-%d %d:%d:%d.%d %d.%ds", &y, &m, &d, &hh, &mm, &ss, &sss, &t1, &t2);
        int en = (hh*3600+mm*60+ss)*1000+sss;
        int T1 = (t1*1000-t1);
        int T2 = (t2 > 0 ? t2-1 : 0);
        int st = en-T1-T2;
        vst.push_back(st);
        ven.push_back(en);
    }
    
    sort(vst.begin(), vst.end());
    sort(ven.begin(), ven.end());
}

int solution(vector<string> lines) {
    
    parse(lines);
    
    int st = 0, en = 1000, cnt = 0, mx = 0;
    int stidx = 0, enidx = 0;
    int stn = vst.size(), enn = ven.size();
    
    while (stidx < stn || enidx < enn) {
        
        while (enidx < enn && ven[enidx] < st) {
            cnt--;
            enidx++;
        }
        while (stidx < stn && vst[stidx] <= en) {
            cnt++;
            stidx++;
        }
        
        mx = max(cnt, mx);
        st++, en++;
    }
    
    return mx;
}