[구현] (프로그래머스 Lv 3) 추석 트래픽

문제

• 문제 링크
• 문제 설명: 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다.
• 입력
  • lines 배열은 N(1 ≦ N ≦ 2,000)개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답완료시간 S와 처리시간 T가 공백으로 구분되어 있다.
  • 응답완료시간 S는 작년 추석인 2016년 9월 15일만 포함하여 고정 길이 2016-09-15 hh:mm:ss.sss 형식으로 되어 있다.
  • 처리시간 T는 0.1s, 0.312s, 2s 와 같이 최대 소수점 셋째 자리까지 기록하며 뒤에는 초 단위를 의미하는 s로 끝난다.
  • 예를 들어, 로그 문자열 2016-09-15 03:10:33.020 0.011s은 "2016년 9월 15일 오전 3시 10분 33.010초"부터 "2016년 9월 15일 오전 3시 10분 33.020초"까지 "0.011초" 동안 처리된 요청을 의미한다. (처리시간은 시작시간과 끝시간을 포함)
  • 서버에는 타임아웃이 3초로 적용되어 있기 때문에 처리시간은 0.001 ≦ T ≦ 3.000이다
• 출력: 초당 최대 처리량

풀이

• 밀리세컨즈까지 문자열에 포함되므로 모든 로그를 ms 단위로 변환
• 요청량이 변하는 부분은 로그의 시작과 끝이므로, 시작부터 시작+1초 구간과 끝부터 끝+1초 구간에서 다른 로그들과 겹친다면 겹치는 개수를 카운트한다.
  • 응답 완료 시간을 기준으로 오름차순 정렬되어 있기 때문에 i번째 로그와 겹치는 로그를 찾을 때는 i+1번째 로그부터 하나씩 탐색해보면 된다.
  • i+1번째 이후부터 로그의 인덱스를 j라고 할 때 로그가 겹치는 구간
    • i번째 로그의 시작 시각 + 1초 >= j번째 로그의 요청 시작 시각
    • i번째 로그의 끝 시각 + 1초 > j번째 로그의 요청 시작 시각
  • 어차피 i+1 이후의 로그들은 응답 완료 시각이 i번째 로그의 응답 완료 시각보다 크거나 같기 때문에 별도로 검사해줄 필요는 없다.
• 카운트한 것들 중 가장 큰 값을 반환
• 정답 코드

#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
using namespace std;

// 시간 포맷을 밀리세컨즈 단위로 변환
int timeToMilli(const string& s) {
    int hh = (s[0]-'0')*10 + (s[1]-'0');
    int mm = (s[3]-'0')*10 + (s[4]-'0');
    int ss = (s[6]-'0')*10 + (s[7]-'0');
    int ms = (s[9]-'0')*100 + (s[10]-'0')*10 + (s[11]-'0');
    return hh*3600000 + mm*60000 + ss*1000 + ms;
}

// 초 단위 시간 포맷을 밀리세컨즈 단위로 변환
int secToMilli(const string& s) {
    int ms = (s[0]-'0') * 1000;
    if (s[1] == '.')
        for (int i = 2, d = 100; s[i] != 's'; i++, d /= 10)
            ms += (s[i]-'0')*d;
    return ms;
}

int solution(vector<string> lines) {
    vector<vector<int>> timestamp;
    for (auto& s : lines) {
        istringstream iss(s);
        string data[3];
        iss >> data[0] >> data[1] >> data[2];
        int endms = timeToMilli(data[1]) + 2999;
        int duration = secToMilli(data[2]);
        int startms = endms - duration + 1;
        timestamp.push_back({startms, endms});
    }
    
    int answer = 0;
    for (int i = 0; i < timestamp.size(); i++) {
        int num = 1;
        int startms = timestamp[i][0] + 1000;
        int endms = timestamp[i][1] + 1000;
        // 다음 로그에 대해 겹치는 개수를 카운트
        for (int j = i+1; j < timestamp.size(); j++)
            if (startms >= timestamp[j][0] or endms > timestamp[j][0])
                num++;
        answer = max(answer, num);
    }
    return answer;
}