🚀 [추석 트래픽] 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;
}
Comments