프로그래머스 문제 - [1차] 추석 트래픽

프로그래머스 [1차] 추석 트래픽 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

응답완료 시간 S와 처리시간 T가 공백으로 구분되어 로드 데이터로 주어집니다.
날짜는 작년 추석인 2016년 9월 15일로 고정됩니다.
T는 최대 3초까지 주어지며 응답시작 시간은 응답완료 시간에 처리시간을 빼준 시간이 됩니다.
주어진 로그 문자열들로 초당 최대 처리량을 구해야합니다.

문제 풀이

임의의 시간대에 1초동안 처리를 진행하거나 끝낸 데이터들의 수를 구하는 문제입니다.
이와 비슷한 문제로는 단속카메라 문제가 있는데 같은 풀이법으로 이번 문제도 해결이 가능합니다.

일단 시간들의 응답완료 시간을 기준으로 오름차순으로 정리해줍니다.
최대한 많은 양의 처리중이거나 처리한 데이터를 알아내기 위하여 앞에서부터 응답완료 시간을 기준으로 1초동안 처리된 데이터들을 찾아주었습니다.
그렇게 되면 최소한 1개의 처리량을 보장받을 수 있습니다.
그 후 계산을 위해 시, 분, 초, 처리시간을 따로 나눠줍니다.

for(string str : lines)
{
    Time t;
    t.hour = stoi(str.substr(11, 2));
    t.minute = stoi(str.substr(14, 2));
    t.second = stof(str.substr(17, 6));
    t.processingTime = stof(str.substr(24, 5));
    timelines.push_back(t);
}

미리 시간들을 응답완료 시간을 기준으로 오름차순으로 정렬을 해두었기 때문에 이전 인덱스에 있는 시간들은 현재 인덱스의 응답완료 시간보다 이전에 처리가 완료되었기 때문에 계산을 하지 않아도 됩니다.
즉 시간들을 timelines배열에 저장을 해두었을 시 timelines[2]가 기준이라면 timelines[0]과 timelines[1]은 처리할 필요가 없습니다.
이후 나머지 데이터들은 응답완료 시간이 기준보다 크기 때문에 기준으로 정한 시간+1초보다 응답시작 시간이 더 적다면 그 데이터는 기준으로부터 1초 사이에 처리된 데이터들에 포함됩니다.

여기서 시간을 비교할 때 1초를 더하면 60초를 넘어 분이 바뀔 때가 있고, 응답시작 시간을 구할 때 0초 이하로 내려가서 분, 초가 바뀌기 때문에 비교가 어렵습니다.
이는 시간들을 시,분을 전부 초로 바꿔 계산하면 좀 더 쉽게 계산이 가능합니다.

bool compareTime(Time a, Time b)
{
    float aTime = (a.hour * 3600) + (a.minute * 60) + a.second + 1 - 0.001f;
    float bTime = (b.hour * 3600) + (b.minute * 60) + b.second - b.processingTime + 0.001f;
    return aTime >= bTime;
}

로그가 처리중인지를 알아내어야 되기 때문에 로그가 시작되는 시점과 끝나는 시점을 기준으로 계산을 하기 위해 0.001초를 더하고 빼주었습니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

struct Time
{
    int hour;
    int minute;
    float second;
    float processingTime;
};

bool compareTime(Time a, Time b)
{
    float aTime = (a.hour * 3600) + (a.minute * 60) + a.second + 1 - 0.001f;
    float bTime = (b.hour * 3600) + (b.minute * 60) + b.second - b.processingTime + 0.001f;
    return aTime >= bTime;
}

int solution(vector<string> lines) {
    int answer = 0;
    vector<Time> timelines;
    
    sort(lines.begin(), lines.end());
    for(string str : lines)
    {
        Time t;
        t.hour = stoi(str.substr(11, 2));
        t.minute = stoi(str.substr(14, 2));
        t.second = stof(str.substr(17, 6));
        t.processingTime = stof(str.substr(24, 5));
        timelines.push_back(t);
    }
    int cnt = 0;
    
    for(int i = 0; i < timelines.size(); i++)
    {
        Time curTime = timelines[i];
        for(int j = i; j < timelines.size(); j++)
        {
            if(i != j && compareTime(curTime, timelines[j]))
            {
                cnt++;
            }
        }
        answer = max(answer, cnt+1);
        cnt = 0;
    }
    
    return answer;
}

출처

https://school.programmers.co.kr/learn/courses/30/lessons/17676