programmers [C++] : 2018 KAKAO BLIND RECRUITMENT 추석 트래픽

programmers.co.kr/learn/courses/30/lessons/17676?language=cpp

코딩테스트 연습 - [1차] 추석 트래픽

문제 설명

---

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

 

입력 형식

1. solution 함수에 전달되는 lines 배열은 N(1 ≦ N ≦ 2,000)개의 로그 문자열로 되어 있으며,

각 로그 문자열마다 요청에 대한 응답완료시간 S와 처리시간 T가 공백으로 구분되어 있다.

2. 응답완료시간 S는 작년 추석인 2016년 9월 15일만 포함하여 고정 길이 2016-09-15 hh:mm:ss.sss 형식으로 되어 있다.

3. 처리시간 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초** 동안 처리된 요청을 의미한다.) (처리시간은 시작시간과 끝시간을 포함)

4. 서버에는 타임아웃이 3초로 적용되어 있기 때문에 처리시간은 0.001 ≦ T ≦ 3.000이다.

5. lines 배열은 응답완료시간 S를 기준으로 오름차순 정렬되어 있다.

 

출력형식

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

 

접근 방법

---

먼저 시간을 분류하고 초 단위 통일했습니다. 처음 방법은 초기 시간 중 가장 작은 시간부터 시작해서 초기 시간 중 가장 긴 시간까지 탐색을 하는 방법으로 진행했습니다!! (시간 초과가 날걸 알았지만 ㅠㅠ 방법이 생각이 안 나서....)

이후에는 시간을 서치 하면서 오차범위로 탐색하는 방법을 선택하여 성공하게 되었습니다.

 

ps) c++ 부동소수점 비교 ***

c++로 구현하면서 double로 저장된 값들을 비교할때 a≥b 같이 사용하면 같은 값이라도 거짓으로 나오는 경우가 있다.

부동소수점 표현에서 발생되는 오차때문에 직접적으로 비교하는건 정확하지 않다.

그래서 위의 코드에서도 epsilon이라는 작은 허용 오차 범위를 정해서

a≥b → abs(a-b)≥epsilon 의 형태로 바꿔서 비교해야한다.

 

코드 

---

[바른 코드]

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

#define abs(x) x<0 ? -x : x
#define epsilon 0.001

using namespace std;


vector<pair<double,double>>range;
vector<int>ans;
int solution(vector<string> lines) {
    int answer = 0;
    for(int i=0;i<lines.size();i++){
        string data=lines[i];
        double hour=stod(data.substr(11,2))*3600;
        double minute=stod(data.substr(14,2))*60;
        double sec=stod(data.substr(17,6));
        double Time=stod(data.substr(24,data.size()-24-1));
      
        double second_time = hour+minute+sec;
        double first_time =second_time-Time; //0.001 더해줄것
        if(first_time<0)first_time=0.000;
        else first_time=first_time+0.001;
        range.push_back(make_pair(first_time,second_time));
    }
    double minimum=9876543.0,maximum=0.0;
    for(int i=0;i<range.size();i++){
        minimum=min(range[i].first,minimum);
        maximum=max(range[i].first,maximum);
    }
    int cnt;
    double start=minimum;
    
    for(int i=0;i<range.size();i++){
    	double begin = range[i].second;
    	double end = begin+0.999;
    	cnt=0;
    	for(int j=i;j<range.size();j++){
    		if(abs(range[j].second-begin)>=epsilon && abs(range[j].first-end)<=epsilon) cnt++;
    		
    	}
    	//최대값 저장
    	answer=max(answer,cnt);
    }
    return answer;
}

[오류 코드]

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

vector<pair<double,double>>range;
vector<int>ans;
int solution(vector<string> lines) {
    int answer = 0;
    for(int i=0;i<lines.size();i++){
        string data=lines[i];
        double hour=stod(data.substr(11,2))*3600;
        double minute=stod(data.substr(14,2))*60;
        double sec=stod(data.substr(17,6));
        double Time=stod(data.substr(24,data.size()-24-1));
      
        double second_time = hour+minute+sec;
        double first_time =second_time-Time; //0.001 더해줄것
        if(first_time<0)first_time=0.000;
        else first_time=first_time+0.001;
        range.push_back(make_pair(first_time,second_time));
    }
    double minimum=9876543.0,maximum=0.0;
    for(int i=0;i<range.size();i++){
        minimum=min(range[i].first,minimum);
        maximum=max(range[i].first,maximum);
    }
    int cnt;
    double start=minimum;
    
    while(true){
        cnt=0;
        for(int i=0;i<range.size();i++){
            if(start > range[i].second || start+1 < range[i].first )continue;
            else cnt++;
        }
        
        answer=max(answer,cnt);
        if(start+0.999>=maximum)break;
        else start=start+0.001;
        //printf("%lf \n",start);
        
    }
    return answer;
}

funny algorithm 0_<