[1차] 추석 트래픽

• 강의실 배정 문제와 비슷하다고 판단

코드

[ 나의 풀이 ]

#include <string>
#include <vector>
#include <sstream>
#include <queue>
#include <iostream>
#include <algorithm>
#define ll long long

using namespace std;
int solution(vector<string> lines) {
    int ans=0;
    priority_queue<ll, vector<ll>, greater<ll>> pq;
    vector<pair<ll,ll>> v;
    // S = 응답완료시간, T = 처리시간
    string D, S;
    double T;
    for(int i=0;i<lines.size();i++)
    {
        stringstream ss(lines[i]);
        ss >> D; // 안씀
        ss >> S; 
        ss >> T;
        ll tot = stoi(S.substr(0,2))*3600000 + stoi(S.substr(3,2))*60000 + stoi(S.substr(6,2))*1000 + stoi(S.substr(9,3));
        ll Ts = T*1000;
        v.push_back({tot-Ts+1, Ts});
    }
    /* 정렬이 중요 - 시작이 짧은 순서대로 정렬해야 함 */
    sort(v.begin(), v.end());
    ll time = v[0].first;
    for(int i=0;i<v.size();)
    {
        int prev = i;
        while(v[i].first <= time)
        {
            pq.push(v[i].first+v[i].second-1);
            i++;
            if(i >= v.size()) break;
        }
        /* +1초 동안은 영향이 있음! 지나서 빼줘야 함 */
        while(pq.top()+1000 <= time) 
            pq.pop();
        ans = max(ans, (int)pq.size());
        if(prev == i and i < v.size()-1) i++;
        time = v[i].first;
    }
    return ans;
}

• 느낀 점
  • 과거에 풀었던 그리디 문제 강의실 배정 문제와 비슷하다고 판단함
    (일정 시간 동안 최대로 겹치는 개수를 구해야 하기 때문)
  • sstream을 매우 유용하게 사용했음
    (공백으로 분리된 값 가져올때는 진짜 최고)
• 핵심
  1) 요청 처리시간이 빠른 순서대로 정렬
  2) priority_queue에 요청이 끝나는 시간을 오름차순으로 정렬해서(먼저 끝나는 순서대로) +1초동안의 영향이 끝날 때 까지 검사!

---

[ 간단한 풀이 ]

#include <string>
#include <vector>
#include <sstream>
#include <queue>
#include <iostream>
#include <algorithm>
#define ll long long

int buff[86400000]; // 1일 = 24시간 = 3600000*24
using namespace std;
int solution(vector<string> lines) {
    int ans=1;
    priority_queue<ll, vector<ll>, greater<ll>> pq;
    vector<pair<ll,ll>> v;
    // S = 응답완료시간, T = 처리시간
    string D, S;
    double T;
    for(int i=0;i<lines.size();i++)
    {
        stringstream ss(lines[i]);
        ss >> D; // 안씀
        ss >> S; 
        ss >> T;
        ll tot = stoi(S.substr(0,2))*3600000 + stoi(S.substr(3,2))*60000 + stoi(S.substr(6,2))*1000 + stoi(S.substr(9,3));
        ll Ts = T*1000;
        v.push_back({tot-Ts+1, Ts});
    }
    for(int i=0;i<v.size();i++)
    {
        int st = v[i].first - 999;
        int end = v[i].first + v[i].second -1;
        for(int s=st;s <= end;s++)
        {
            if(s < 0 or s > 86400000) continue;
            buff[s]++;
            ans = max(ans, buff[s]);
        }
    }
    return ans;
}

• 로직
  : int buff[]를 두고 지나가는 시간에 값을 1씩 증가시켜서 모든 로그에 대해 실행시키면서 겹치는 최대값을 수시로 저장!
  : 이 그림을 1차원 배열에 옮긴것처럼 구현

• 주의할 점
  1) 값은 유효범위가 1초이기 때문에 앞이나 뒤로 1초만큼 범위를 추가 해줘야 함
  --> 해당 과정에서는 1000이 아니라 999로 추가 해야 한다
  (이유는 두 로그가 겹치는 기준은 정확히 같을 경우가 아니라 작거나 같아지는 상황임
  즉, 시작과 끝은 포함하면서 범위를 늘리려면 1000이 아니라 999만큼 범위 추가)
  0.001 ~ 1.000 까지가 1초 범위임 - 주의