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

문제 링크

 

풀이

문자열로 되어 있는 시간 로그를 실제 숫자로 변경해 주어진 로그에서 시작 시간을 구해, 시작 시간과 완료 시간을 pair로 가지는 벡터에 넣습니다. 1초 동안 최대로 걸려 있는 처리량을 구하는 것이 답입니다. 문제를 보면 lines 배열은 응답완료시간을 오름차순 정렬이 되어 있습니다.

이 말은 n번째 로그의 완료시간은 무조건 n-1보다 늦다는 이야기가 됩니다. 즉 시작 시간을 기준하면 됩니다. 예제 2를 보면 첫 번째 로그가 끝나는 시점과 두 번째 로그의 시작 지점이 1초에 같이 속하기 때문에, 최대 2개가 카운트 된다는 것이 힌트입니다. 1초라는 간격을 적용했을 때 카운트할 수 있는 최대값을 찾는 것이 목표입니다. 즉 n번째의 시작 시간이 n-1번째의 완료시간 + 999ms보다 같거나 작으면 되는 것입니다.

 

코드

#include <string>
#include <vector>
using namespace std;
int solution(vector<string> lines) 
{
    int answer = 1;
    vector<pair<double, double>> new_lines;
    size_t size = lines.size();
    for (size_t i = 0; i < size; ++i)
    {
        string str = lines[i];
        int hh = stoi(str.substr(11, 2)) * 3600;
        int mm = stoi(str.substr(14, 2)) * 60;
        int ss = stoi(str.substr(17, 2));
        double mill = stoi(str.substr(20, 3)) / 1000.0;
        double end_time = hh + mm + ss + mill; // 응답완료 시간

        string temp = str.substr(24);
        double p_time = stod(temp.substr(0, temp.length() - 1));
        double start_time = end_time - p_time + 0.001;

        new_lines.push_back({ start_time, end_time });
    }
    for (size_t i = 0; i < size - 1; ++i)
    {
        int count = 1;
        double end = new_lines[i].second + 1;
        for (size_t j = i + 1; j < size; ++j)
        {
            double start = new_lines[j].first;
            if (start < end)
                ++count;
        }
        answer = answer < count ? count : answer;
    }
    return answer;
}