문제
- 문제 링크
- 문제 설명: 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 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;
}
'Algorithm > Problem Solving' 카테고리의 다른 글
[구현] (프로그래머스 Lv 4) 블록 게임 (0) | 2021.04.24 |
---|---|
[PriorityQueue] (프로그래머스 Lv 3) 셔틀버스 (0) | 2021.04.24 |
[String, Trie] (프로그래머스 Lv 4) 자동완성 (0) | 2021.04.24 |
[PriorityQueue] (프로그래머스 Lv 4) 무지의 먹방 라이브 (0) | 2021.04.24 |
[String, Trie] (프로그래머스 Lv 4) 가사 검색 (0) | 2021.04.24 |