추석 트래픽

 

programmers.co.kr/learn/courses/30/lessons/17676

코딩테스트 연습 - [1차] 추석 트래픽

추석 트래픽 문제를 풀이한다.

접근 방법이 떠오르지 않아 힌트를 참고하였는데, 핵심은 구간을 어떻게 판정해야 하는가이다.

먼저, 문자열로 된 시각들을 1초의 구간에 포함되는 확인하기 위해, 변환하는 과정이 필요하다. 여기서 double, int로 해도 되지만, 혹시나 오버플로가 날까봐 long long으로 하였다.

이 때, 시작 시각과 끝 시각을 구하여 vector로 관리하는데, 끝 시각을 이용하여 시작 시간을 구할 때 +1을 해준다.

이렇게 하는 이유는 처리 시간의 기준이 시작 시간과 끝 시간을 포함하기 때문이다.

 

위의 과정을 수행하면 vector에는 시작, 끝 시간이 포함되어 있을 것이다. 여기서 방법이 여러 가지로 나뉘는데,

첫 번째는 슬라이딩 윈도우로 각 로그마다 1초 구간에 있는 로그들을 카운트한다.

그런데 기준점을 잘 잡아야 하는데 시점에서부터 미래 혹은 과거까지의 1초인지에 따라 정답여부가 갈린다.

두 번째는 더 간단한 방법인데, 입력 조건에서 응답 완료 시간을 기준으로 오름차 정렬된 값들이 들어오기 때문에,

v[n + 1].start < v[n].end + 1000(ms)라면, 1초 내의 구간에 포함된다.

즉 코드로 나타내면 다음과 같다.

for(int i = 0; i < window.size(); i++){
        int count = 0;
        long long wend = window[i].second + 1000;
        for(int j = i; j < window.size(); j++){
            if(wend > window[j].first)
                count++;
        }
        answer = max(answer, count);
    }

정답 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
vector<string> startv;
vector<pair<long long, long long>> window;
int get_ms_dur(string& str)
{
    int total = 0;
    int digit = 1000;
    for(int i = 0; i < str.size(); i++){
        if('0' <= str[i] && str[i] <= '9'){
            total += (str[i] - '0') * digit;
            digit /= 10;
        }
    }
    return total;
}
int solution(vector<string> lines) {
    int answer = 0;
    for(const auto& str : lines){
        string hour = str.substr(11, 2);
        string min = str.substr(14, 2);
        string sec = str.substr(17, 2);
        string ms = str.substr(20, 3);
        long long end = stoi(hour) * 3600 + stoi(min) * 60 + stoi(sec);
        end *= 1000;
        end += stoi(ms);
        
        string dur = str.substr(24);
        long long start = end - get_ms_dur(dur) + 1;
        window.push_back({start, end});
    }
    for(int i = 0; i < window.size(); i++){
        int count = 0;
        long long wend = window[i].second + 1000;
        for(int j = i; j < window.size(); j++){
            if(wend > window[j].first)
                count++;
        }
        answer = max(answer, count);
    }
    return answer;
}