"2018 KAKAO BLIND RECRUITMENT > [1차] 추석 트래픽" 풀이

문제: programmers.co.kr/learn/challenges?selected_part_id=9317

 

 

문제 풀이:

 

Point 1. "응답 완료 시간S는 작년 추석인 2016년 9월 15일만 포함" 

• 즉, 날짜는 크게 신경 쓰지 않아도 된다.

Point 2. 각 날짜 및 시간을 ms 단위로 변경하자

• = (시간*$60^2$ + 분*60 + 초)*1000 + 소수점 이하
• 예: 01:00:04.002s -> 3604002ms

Point 3. 처리 시작 시간 구하기 

• 입력은 "2016-09-15 01:00:04.001 2.0s" 형태로 주어진다. 
• 먼저 응답 완료 시간(S)을 [Point 2]와 같이 변경한다.
• 처리 시간(T)도 이와 같이 변경해준다. 
  • 이때, 처리 시간의 형태는 다양할 수 있으므로 주의해야 한다.
  • '소수점이 존재 여부', '소수점 길이'가 다를 수 있기 때문에 나는 convertSec라는 함수를 만들어 하단에 보이는 것과 같이 처리하였다.

Point 4. 초당 최대 처리량 계산하기

• "응답 완료 시간(S)을 기준으로 오름차순 정렬"되어있다.
• 하나를 기준으로 잡고, 그 작업 시간의 끝과 시작을 다음 작업들의 시작 시간과 비교하면 된다.
• 즉, 어떤 응답의 [시작 시간, 시작 시간+1] or [끝 시간, 끝 시간+1]에 겹치는 작업 이 존재하는지 찾으면 된다.

 

* testcase 3번과 18번을 틀리는 경우

처음에는 현재 비교 대상(i)과 이후 값(p)이 겹치지 않으면 while문을 break 해서 끝내버렸다. 

하지만, 다음과 같은 상황이 존재할 수 있다.

-> lines[0]과 lines[1]는 겹치지 않지만, lines[0]과 lines[2]는 겹치는 경우

 

즉, 겹치지 않는 것이 나왔다고 연산을 끝내지 않고 끝까지 진행하도록 하면, 해당 테스트 케이스를 통과할 수 있다.

 

마지막에 수정하다 보니, 기존에 생각과는 다르게 다소 비효율적인 풀이가 된 것 같다. 나중에 다시 풀어봐야겠다 ㅠ

#include <iostream>
#include <string>
#include <vector>
#include <cmath>

using namespace std;


int convertTime(string time){
    int hour = stoi(time.substr(11,2));
    int min = stoi(time.substr(14,2));
    int sec = stoi(time.substr(17,2));
    int ms = stoi(time.substr(20,3));
    int convertedTime = (hour*60*60+min*60+sec)*1000+ms;
    return convertedTime;
}

int convertSec(string time){
    string sec = "";
    int p =0;
    while(true){
        if(time[p]=='.'||time[p]=='s') {
            p++;
            break;
        }
        sec+=time[p];
        p++;
    }
    int lenAfterDot =0;
    while(p<time.size()){
        if(time[p]=='s') break;
        sec+=time[p];
        lenAfterDot++;
        p++;
    }
    return stoi(sec)*pow(10,3-lenAfterDot);
}


int solution(vector<string> lines) {
    int answer = 0;
    int linesLen = lines.size();
    for(int i=0;i<linesLen;i++){
        int endTime = convertTime(lines[i]);
        int startTime = endTime - convertSec(lines[i].substr(24))+1;
        
        int cnt=0;
        int p=i+1;
        while(p<linesLen){
            int next = convertTime(lines[p])-convertSec(lines[p].substr(24))+1;
            if((next<=endTime+999)||(next<=startTime+999) ){
                cnt++;
                answer= max(answer, cnt);
            }
            p++;
        }
    }
    
    return answer+1;
}