[Programmers] [1차] 추석 트래픽

1초 동안 가장 많이 처리하는 양을 구하는 문제이다.

문제 풀이 전략
시간을 가지고 놀아야 하는 거라 계산이 좀 까다로웠다.

소수점 아래 초 단위를 쉽게 다루기 위해 ms로 변환해 주었다.

시간에는 x3600000, 분에는 x60000, 초에는 x1000 을 해 준뒤 소수점 초단위와 다 더해주면 된다.

그리고 시작시간과 끝나는 시간을 벡터에 저장해 주었다.

끝나는 시간만 주어져 있기 때문에 시작시간을 구해야 하는데 이는
끝나는 시간 - 걸린시간 + 1 을 통해 구할 수 있다.

트래픽 양이 변화하는 시간은 각 작업의 시작시간과 끝시간이다.

즉 각 작업의 시작시간 부터 1초, 끝시간 부터 1초를 구간으로 하여 그 구간 내에 속하는 모든 작업의 양을 세주면 된다.

구간을 구하는 방법은 시작시간 + 1000 - 1로 하면 된다. 이 때 시작시간은 실제 시작시간과 실제 끝나는 시간이 된다.

각 작업 별로 두 구간에 대해 수행되는 작업을 모두 세 주면 된다.

만약 1ms 단위로 윈도우를 옆으로 한칸씩 옮겨가며 찾는다면 너무 많은 시간이 걸리게 될 것이다.

코드

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

int solution(vector<string> lines) { // s - t + 0.001 -> 시작시간
    int answer = 0;
    vector<pair<int,int>> v;
    
    for(int i=0;i<lines.size();i++){
        int hh = (lines[i][11]-'0')*10 + lines[i][12]-'0';
        int mm = (lines[i][14]-'0')*10 + lines[i][15]-'0';
        int ss = (lines[i][17]-'0')*10 + lines[i][18]-'0';
        int sss = (lines[i][20]-'0')*100 + (lines[i][21]-'0')*10 + lines[i][22]-'0';
        int tt = 0;
        int tmp = 1000;
        for(int j=24;j<lines[i].size()-1;j++){
            if(lines[i][j] == '.')
                continue;
            tt += (lines[i][j]-'0')*tmp;
            tmp /= 10;
        }
        
        int start = hh*3600000+mm*60000+ss*1000+sss - tt + 1;
        int end = hh*3600000+mm*60000+ss*1000+sss;
        if(start < 0)
            start = 0;
        if(end > 86399999)
            end = 86399999;
        v.push_back(make_pair(start, end));
    }
    int mi = -1;
    for(int i=0;i<v.size();i++){
        int start = v[i].first;
        int end = v[i].second;
        int cnt = 0;
        int e_time = start + 1000 - 1;
        if(e_time > 86399999)
                e_time = 86399999;
        for(int j=0;j<v.size();j++){
            if(v[j].second < start || v[j].first > e_time)
                continue;
            cnt++;
        }
        mi = max(mi,cnt);
        cnt = 0;
        e_time = end + 1000 - 1;
        if(e_time > 86399999)
                e_time = 86399999;
        for(int j=0;j<v.size();j++){
            if(v[j].second < end || v[j].first > e_time)
                continue;
            cnt++;
        }
        mi = max(mi,cnt);
    }
    
    answer = mi;
    return answer;
}

출처 : 프로그래머스
https://programmers.co.kr/learn/courses/30/lessons/17676