[프로그래머스 - 추석 트래픽]

[프로그래머스 - 추석 트래픽]
https://programmers.co.kr/learn/courses/30/lessons/17676

방학 내내 삼성 기출만 풀어보다가 오랜만에 프로그래머스에 도전했다. 레벨 3 문제답게 쉽지 않았고, 결국 다른 사람의 풀이를 참고했다.

풀이

string 타입으로 주어지는 시간을 double 타입으로 바꿔줄 수 있다는 생각을 해내지 못했다. double 타입으로 바꿔주게 되면 1초 간격 안에 다른 트래픽이 들어오는지 검사하기 상당히 간편해진다.

double completeTime = stod(lines[i].substr(11,2)) * 3600 + 
	stod(lines[i].substr(14,2)) * 60 + 
    stod(lines[i].substr(17,2)) + 
    stod(lines[i].substr(20,3)) / 1000.0;
    
string temp = lines[i].substr(24);

double throughPutTime = stod(temp.substr(0, temp.size()-1));

double startTime = completeTime - throughPutTime + 0.001;

double 타입으로 바꿔준 덕분에 startTime을 구하는 작업이 매우 수월해졌다. 이전에 string 여기저기에서 지저분하게 파싱해서 연산하던 작업이 모두 사라졌다.

이렇게 구해준 startTime, completeTime을 pair<string,string> 페어에 넣어주고, 생성된 모든 페어를 벡터 responses에 저장한다.

그 다음 1초 간격에 다른 트래픽이 들어오는가를 판단하는 부분이 또 하나의 관문이다. 문제에 응답 완료 시간을 기준으로 정렬이 되어 있다고 제시되어 있다. 이 부분에서 아이디어를 얻어낼 수 있었다.

사진에서 트래픽이 위아래로 두 개 있을 때, 위에 있는 트래픽이 이전 트래픽, 밑에 있는 트래픽이 현재 트래픽이라고 하겠다.
start + 1은 이전 트래픽의 응답 시작 시간 + 1초가 되는 시간이고, end + 1은 이전 트랙픽의 응답 완료 시간 + 1초가 되는 시간이다.

현재 트래픽의 응답 완료 시간은 최소 이전 트래픽의 응답 완료 시간과 동일하다 따라서 현재 트래픽의 응답 시작 시간을 기준으로 크게 4가지의 경우로 나뉠 수 있다. 이 중 위의 3가지 경우는 "겹쳐있는" 경우로 초당 최대 트래픽 개수에 카운트 되어야 한다. 하지만 가장 마지막 경우는 end + 1 시간보다 현재 트래픽의 응답 시작 시간이 나중이기 때문에 겹쳐있지 않게 된다.

따라서 겹쳐있는지, 즉 초당 최대 트래픽 개수에 카운트 되어야 하는지를 판단하기 위해서는 (이전 트래픽의 응답 시작 시간 + 1 > 현재 트래픽의 응답 시작 시간) 또는 (이전 트래픽의 응답 완료 시간 + 1 > 현재 트래픽의 응답 시작 시간)이 참인지 판단하면 된다.

C++ 코드

#include <string>
#include <vector>

using namespace std;


int solution(vector<string> lines) {
    int ans = 1;
    vector<pair<double,double>> responses;
    
    for(int i=0;i<lines.size();++i) {
        double completeTime = stod(lines[i].substr(11,2)) * 3600 + stod(lines[i].substr(14,2)) * 60 + stod(lines[i].substr(17,2)) + stod(lines[i].substr(20,3)) / 1000.0;
        string temp = lines[i].substr(24);
        double throughPutTime = stod(temp.substr(0, temp.size()-1));
        double startTime = completeTime - throughPutTime + 0.001;
        
        responses.push_back(make_pair(startTime, completeTime));
    }
    
    for(int i=0;i<responses.size();++i) {
        double start = responses[i].first;
        double end = responses[i].second;
        
        int tmp = 1;
        for(int j=i+1;j<responses.size();++j) {
            if(start + 1 > responses[j].first || end + 1 > responses[j].first) {
                tmp++;
            }
        }
        
        ans = max(ans, tmp);
    }
    
    return ans;
}