문제링크 입니다

🚀 [추석 트래픽] Lv. 3 문제

모든 시간을 밀리초로 나타내어 시작시간과 응답완료시간을 pair로 벡터에 저장한다. 이후 응답완료시간을 기준으로 정렬 되어 있으므로, 2중 for문을 돌면서 간단하게 시간이 중복된 것을 count하며 문제를 해결한다.

💎 전체 코드는 다음과 같습니다.

// DP 로 해결한다.
#include <string>
#include <vector>
#include <iostream>
#include <utility> // pair
#include <algorithm>
using namespace std;
// 시작과 완료 시간
vector<pair<int, int> > times;

// 요청 완료시간을 기준으로 정렬 되어 있으므로
// 2중 for 문을 돌면서 첫번째 for 문 기준으로 중복 된 시간을 count한다.
int solve(){
    int max = -1;
    for(int i=0; i<times.size(); i++){
        int count = 1;
        int endPoint = times[i].second +1000 ; //1초 동안
        for(int j = i+1 ;j<times.size(); j++){
            if(times[j].first < endPoint){
                count++;
            }
        }
        max = (count > max) ? count : max;
    }
    return max;
}
// 모든 시간을 millisecond 로 표현한다.
void preprocessing(vector<string> &lines){
    int n = lines.size();
    for(int i=0; i<n; i++){
        int hour = stoi(lines[i].substr(11,3));
        int min = stoi(lines[i].substr(14,3));
        int sec = stoi(lines[i].substr(17,3));
        int milli = stoi(lines[i].substr(20,4));
        double takes = stod(lines[i].substr(24,lines[i].rfind('s')));
        int end_time = hour * 3600 * 1000 + min * 60 * 1000 + sec * 1000 + milli;
        int start_time = end_time - takes * 1000 + 1;
        times.push_back(make_pair(start_time,end_time));        
    }
}
int solution(vector<string> lines) {
    int answer = 0;
    preprocessing(lines);
    answer = solve();
    times.clear();
    return answer;
}

presenToN

Comments