[알고리즘 풀이 분석] 프로그래머스 추석 트래픽 (2018 Kakao Blind Recruitment)

오늘 풀어본 문제는 프로그래머스 추석 트래픽 이다!
알고리즘보다는 시간 처리 능력, 문제 이해 능력이 더 주가 되었던 문제가 아니낙 싶다.. 그래서 난 못했다 ㅋㅋㅋㅋ 나만 문제 이해 안되는거냐구요,,, 그림도 뭔소리인가 싶고,, 설명이랑 일치도 안하는 것 같고,, 참내,,
제가 이상하다면 죄송합니다 ㅎ,,,

프로그래머스 추석 트래픽

이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다.

입출력

입력 형식

• solution 함수에 전달되는 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이다.
• lines 배열은 응답완료시간 S를 기준으로 오름차순 정렬되어 있다.

출력 형식

• solution 함수에서는 로그 데이터 lines 배열에 대해 초당 최대 처리량을 리턴한다.

나의 풀이

먼저 시간과 관련된 문제를 여러번 연습한 결과 입력되는 다양한 시간들은 무조건 하나로 통일시키는 것이 관건이라는 것을 깨달았다. 가장 작은 단위인 1/1000초 (ms) 까지 계산해서 입력되는 모든 트래픽들 lines의 원소의 시작시간 startTime 과endTime를 묶어서 vector<pair<int, int>> traffics 에 저장하였다.

이후 나는 처음에 dp를 사용하려 했으나 문제를 제대로 이해하지 못했던 바,, 야심찬 나의 dp 계획은 와르르 무너지고 결국 그냥 단순한 2중 포문을 사용해서 해결하였다.

방법은 매우 간단하다.

입력되는 lines 는 응답 처리 완료 시간을 기준으로 하여 정렬되어 있기 때문에 endTime 을 기준으로 하여 해당 종료 시간 + 1초(1000ms) 보다 startTime 이 앞서는 트래픽을 count 해 준다.

이후 count 한 값이 최댓값이면 정답을 갱신한다. 종료 시간 + 1초(1000ms) 를 기준으로 하는 이유는 문제 조건 중 "응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청" 이라는 조건을 고려한 것이다.

그리 어렵지 않은 문제인데 나에게는 문제 조건 자체를 이해하는 것이 더 까다로웠던 것 같다.

코드

#include <string>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

int solution(vector<string> lines) {
    int answer = 0;
    vector<pair<long long, long long>> traffics;

    for(int i=0; i<lines.size(); i++){
        vector<string> tokens;
        stringstream ss1(lines[i]);
        string temp;

        while(getline(ss1, temp, ' ')){
            tokens.push_back(temp);
        }

        vector<string> frags;
        stringstream ss2(tokens[1]);

        while(getline(ss2, temp, ':')){
            frags.push_back(temp);
        }

        long long endTime = 0;
        endTime += stoi(frags[0]) * 3600 * 1000;
        endTime += stoi(frags[1]) * 60 * 1000;
        endTime += stoi(frags[2].substr(0,2)) * 1000;
        endTime +=stoi(frags[2].substr(3, frags[2].size()-3));

        tokens[2] = tokens[2].substr(0, tokens[2].size()-1);
        bool dot = false;
        int dotAt = -1;
        for (int j = 0; j < tokens[2].size(); ++j) {
            if (tokens[2][j] == '.'){
                dot = true;
                dotAt = j;
                break;
            }
        }

        long long runtime = 0;
        if (!dot){
            runtime += stoi(tokens[2]) * 1000;
        }else{
            runtime += stoi(tokens[2].substr(0, dotAt)) * 1000;
            runtime += stoi(tokens[2].substr(dotAt+1, tokens[2].size()-dotAt-1));
        }


        long long startTime = endTime - runtime + 1;

        traffics.push_back(make_pair(startTime, endTime));
    }

    if (traffics.size() > 0) {

        for(int i=0 ;i<traffics.size(); i++) {
            int count = 1;
            for (int j = i+1; j < traffics.size() ; ++j) {
                if(traffics[j].first < traffics[i].second + 1000) count++;
            }
            if (answer < count) answer = count;
        }
    }

    return answer;
}