카카오 1차 온라인 코딩테스트 7번 문제(17.09.16)

안녕하세요~ 코딩하는 JAY 입니다!! 오늘은 대망의 마지막 7번문제를 포스팅하겠습니다.

(끼야옭~~~~~~~~)

7번문제는 가장 어려웠던 문제인 것 같습니다. 흠... 어렵다기 보다는 생각이 조금 필요한 문제였던 것 같아요. 

일단 문제를 한번 보죠~

문제 및 풀이 링크 : http://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/

7. 추석 트래픽(난이도: 상)

이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 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

• 입력: [ “2016-09-15 01:00:04.001 2.0s”, “2016-09-15 01:00:07.000 2s” ]
• 출력: 1

예제 2

• 입력: [ “2016-09-15 01:00:04.002 2.0s”, “2016-09-15 01:00:07.000 2s” ]
• 출력: 2
• 설명: 처리시간은 시작시간과 끝시간을 포함하므로 첫 번째 로그는 01:00:02.003 ~ 01:00:04.002에서 2초 동안 처리되었으며, 두 번째 로그는 01:00:05.001 ~ 01:00:07.000에서 2초 동안 처리된다. 따라서, 첫 번째 로그가 끝나는 시점과 두 번째 로그가 시작하는 시점의 구간인 01:00:04.002 ~ 01:00:05.001 1초 동안 최대 2개가 된다.

예제 3

• 입력: [ “2016-09-15 20:59:57.421 0.351s”, “2016-09-15 20:59:58.233 1.181s”, “2016-09-15 20:59:58.299 0.8s”, “2016-09-15 20:59:58.688 1.041s”, “2016-09-15 20:59:59.591 1.412s”, “2016-09-15 21:00:00.464 1.466s”, “2016-09-15 21:00:00.741 1.581s”, “2016-09-15 21:00:00.748 2.31s”, “2016-09-15 21:00:00.966 0.381s”, “2016-09-15 21:00:02.066 2.62s” ]
• 출력: 7
• 설명: 아래 타임라인 그림에서 빨간색으로 표시된 1초 각 구간의 처리량을 구해보면 (1)은 4개, (2)는 7개, (3)는 2개임을 알 수 있다. 따라서 초당 최대 처리량은 7이 되며, 동일한 최대 처리량을 갖는 1초 구간은 여러 개 존재할 수 있으므로 이 문제에서는 구간이 아닌 개수만 출력한다.

문제풀이

이번문제 역시 문자열로 시간을 입력받네요 ㅎㅎ 7번 문제의 핵심은 임의의 시간에서 1초동안 얼마나 많은 처리를 했는지를 구하는 것입니다. 

다시한번 강조하지만 임의의 시간 입니다!

처음에 저는 그냥 로그의 첫 시간부터 마지막 시간까지 1초씩 증가하여 그 구간의 최대처리량을 구하는줄 알았습니다.

아니나 다를까.. 카카오는 그렇게 호락호락하지 않았습니다. 어느 구간이든 최대 처리량을 구하는게 이 문제의 핵심이죠. 

1. '2016-09-15'의 로그데이터가 아니면 vector에서 삭제해 준다.

2. string으로 받은 시간을 계산하기 쉽게 숫자로 변환해 준다.

3. 임의의 구간에서 1초동안 최대 처리량을 구한다.

알고리즘이 실행되는 전체적인 구조는 이렇습니다. 다만, 3번의 처리방법에서 좀 많은 생각을 했던 것 같습니다. 임의의 구간이기 때문에 0.001초 부터 증가시켜서 다 처리하기에는 Time out이고, 처리해야할 데이터 양도 많습니다.

이 부분은 고민끝에 카카오 해설을 참고했는데요. 요청량이 변하는 구간은 로그의 시작과 끝입니다. 즉, 각 로그의 시작과 끝에서 최대 처리량 체크를 하면 되겠습니다.  2 * n^2의 시간복잡도이며 빅오로 정리하면 O(n^2)으로 처리가 가능합니다.

그림에서 보시면 숫자들(1~C)이 데이터량을 체크하는 시작 구간입니다.

자 이제 코드를 한번 살펴 보겠습니다.

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
using namespace std;
int solution(vector <string> lines);
int main(void)
{
    string arr[] = {"2016-09-15 01:00:04.001 2.0s", "2016-09-15 01:00:07.000 2s"};
    string arr2[] = {"2016-09-15 01:00:04.002 2.0s", "2016-09-15 01:00:07.000 2s"};
    string arr3[] = {"2016-09-15 20:59:57.421 0.351s", "2016-09-15 20:59:58.233 1.181s", 
                    "2016-09-15 20:59:58.299 0.8s", "2016-09-15 20:59:58.688 1.041s", 
                    "2016-09-15 20:59:59.591 1.412s", "2016-09-15 21:00:00.464 1.466s", 
                    "2016-09-15 21:00:00.741 1.581s", "2016-09-15 21:00:00.748 2.31s", 
                    "2016-09-15 21:00:00.966 0.381s", "2016-09-15 21:00:02.066 2.62s"};
    vector <string> testCase(arr, arr + (sizeof(arr) / sizeof(arr[0])));
    vector <string> testCase2(arr2, arr2 + (sizeof(arr2) / sizeof(arr2[0])));
    vector <string> testCase3(arr3, arr3 + (sizeof(arr3) / sizeof(arr3[0])));
    
    cout << fixed; // 소수점 3자리 보여주기 고정
    cout.precision(3);
 
    cout << "최대 트래픽 : " << solution(testCase) << endl;
    cout << "최대 트래픽 : " << solution(testCase2) << endl;
    cout << "최대 트래픽 : " << solution(testCase3) << endl;
        
    return 0;
}                                
    
// string으로 받은 시각을 double형식의 초단위로 변경(계산하기 쉽게)
double StringToMintime(bool timeFlag, string time)
{
    double secTime = 0;
    double msec = 0;
    int sec = 0;
    
    if(timeFlag == true) {
        int hour = ((time[0] - '0') * 10 + (time[1] - '0')) * 3600;
        int min = ((time[3] - '0') * 10 + (time[4] - '0')) * 60;
        sec = (time[6] - '0') * 10 + (time[7] - '0');
        msec = ((time[9] - '0') / pow(10, 1)) + ((time[10] - '0') / pow(10, 2)) + ((time[11] - '0') / pow(10, 3)); 
        secTime = (double)(hour + min + sec) + msec;
    } else {
        for(int i = 0; i < time.size() - 1; i ++) {
            if(i == 0)     sec = (time[0] - '0');
            else if(i > 1) msec += (time[i] - '0') / pow(10, i - 1); 
        }
        secTime = (double)sec + msec - 0.001;
    }
 
    return secTime;
}
 
int solution(vector <string> lines)
{
    double lastlogTime = StringToMintime(true, lines[lines.size() - 1].substr(11, 12)); // 마지막 로그가 끝나는 시간
    double firstlogTime = 0; // 로그가 시작되는 시간(각 로그의 처음과 끝을 기준으로 대입해줌)
    int maxTraffic = 0; // 최대 트래픽
    int answer = 0;    
 
    // 1. 날짜 체크(2016-09-15가 아닌 날짜의 로그 삭제)
    for(int i = lines.size() - 1; i >= 0; i --) {
        if(lines[i].find("2016-09-15", 0) == string::npos) lines[i].erase();
    }
    
    // 2. 각 로그의 시작과 끝을 기준으로 트래픽 체크(시작과 끝에서 요청량이 변하기 때문)
    for(int i = 0; i < lines.size() * 2; i ++) {
        if((i % 2) == 0) firstlogTime = StringToMintime(true, lines[i / 2].substr(11, 12)) - StringToMintime(false, lines[i / 2].substr(24));
        else firstlogTime = StringToMintime(true, lines[i / 2].substr(11, 12));
 
        // 3. 체크시작할 로그 시간부터 마지막 로그시간까지 1초씩 증가하여 트래픽 체크
        for(float j = firstlogTime; j < lastlogTime; j ++) {
        
            // 4. 1초 단위의 트래픽 구간(Time)에 총 몇개의 로그가 처리되는지 체크
            int tempTraffic = 0;
            for(int k = 0; k < lines.size(); k ++) {
                double startTime = StringToMintime(true, lines[k].substr(11, 12)) - StringToMintime(false, lines[k].substr(24));
                double endTime = StringToMintime(true, lines[k].substr(11, 12));
            
                // 5. 트래픽 체크 구간보다 작거나 큰경우를 제외한 모든경우(0.001초라도 걸치는 부분)
                if(!(startTime < j && endTime < j) && !(startTime > j + 1 && endTime > j + 1)) tempTraffic += 1;
            }
            // 6. 최대 트래픽 체크
            if(tempTraffic > maxTraffic) maxTraffic = tempTraffic;
        }
    }
 
    answer = maxTraffic;
    return answer;
}

첫번째로, solution함수에서 "1. 날짜체크"에서 입력받은 배열에서 "2016-09-15"가 없으면 erase()함수로 지워버립니다.

이때  vector의 크기도 함께 줄어듭니다. 

두번째로는, 문자열로 받은 시간을 초단위의 숫자로 바꿔줘야 합니다.

// string으로 받은 시각을 double형식의 초단위로 변경(계산하기 쉽게)
double StringToMintime(bool timeFlag, string time)
{
    double secTime = 0;
    double msec = 0;
    int sec = 0;
    
    if(timeFlag == true) {
        int hour = ((time[0] - '0') * 10 + (time[1] - '0')) * 3600;
        int min = ((time[3] - '0') * 10 + (time[4] - '0')) * 60;
        sec = (time[6] - '0') * 10 + (time[7] - '0');
        msec = ((time[9] - '0') / pow(10, 1)) + ((time[10] - '0') / pow(10, 2)) + ((time[11] - '0') / pow(10, 3)); 
        secTime = (double)(hour + min + sec) + msec;
    } else {
        for(int i = 0; i < time.size() - 1; i ++) {
            if(i == 0)     sec = (time[0] - '0');
            else if(i > 1) msec += (time[i] - '0') / pow(10, i - 1); 
        }
        secTime = (double)sec + msec - 0.001;
    }
 
    return secTime;
}

timeFlag 변수가 TRUE일 경우에는 "01:00:04.001" 형식의 문자열을 받아 double형식의 초단위 숫자로 변환해 줍니다.

FALSE일 경우에는 "2.0s" 형식의 처리시간을 마찬가지로 double형식의 초단위 숫자로 변환해 줍니다.

timeFlag 변수가 FALSE일 경우 마지막 "secTime = (double)sec + msec - 0.001;" 이 코드에서 - 0.001을 해준 이유는 처리시간이 시작시간부터 끝시간 까지이기 때문입니다. 

예를들어 로그의 시간이 1분 10초이고, 처리시간이 10초라고 했을때(1초단위의 처리라고 가정하에), 로그의 시작시간은 1분 1초입니다. 왜냐하면 1분 1초부터 1분 11초 전까지가 데이터가 처리된 시간이며, 처리시간은 시작시간과 끝시간을 포함하기 때문입니다. 그리고 처리단위는 0.001이기 때문에 - 0.001을 해준것입니다.

뭔가 설명이 어려운 것 같은데.. 무튼 이렇습니다.(ㅜㅜ 저의 한계인가 봅니다.)

추가로 float가 아닌 double을 반환형으로 한 중요한 이유가 있습니다!!!!

       

1. float를 사용하여 계산한 경우                     2. double을 사용하여 계산한 경우

보시다시피 float를 사용했을 경우 값이 제대로 계산되지 않습니다. 

그 이유는 컴퓨터는 내부적으로 수를 2진법으로 표현합니다. 그래서 0.0001 같은 수를 정확히 표현할 수 없기 때문입니다.

http://karmainearth.tistory.com/143

위 블로그를 참고하시면 좀 더 자세한 내용을 알 수 있습니다. double도 마찬가지로 정확한 값을 표현할 수 없습니다. 

다만, float 보다 크기때문에 float보다는 정확한 소수값을 표현할 수 있습니다. (처음에 제 코드가 이상한 줄 알았습니다... 문제를 풀면 풀수록 새로운 걸 많이 알게 되네요 ㅎㅎ 양파 같은 프로그래밍)

마지막으로 "2. 각 로그의 시작과 ~~" 이 부분을 보겠습니다.

// 2. 각 로그의 시작과 끝을 기준으로 트래픽 체크(시작과 끝에서 요청량이 변하기 때문)
    for(int i = 0; i < lines.size() * 2; i ++) {
        if((i % 2) == 0) firstlogTime = StringToMintime(true, lines[i / 2].substr(11, 12)) - StringToMintime(false, lines[i / 2].substr(24));
        else firstlogTime = StringToMintime(true, lines[i / 2].substr(11, 12));
 

위 코드를 보면 "if((i % 2 == 0)" 의 조건문이 있는데 최대처리를 체크하는 구간의 시작이 각 로그의 시작과 끝이기 때문에 i가 짝수이면 로그의 시작, 홀수이면 로그의 끝시간을 구하게 됩니다. 코드의 결과를 확인해보면~

이상으로 기나긴 "카카오 1차 온라인 코딩테스트" 문제풀이를 마치겠습니다.

7번문제는 제가 풀이방법을 정확히 이해 했는지 잘 모르겠네요 ㅠㅠ  혹시나 제 풀이방법이 틀렸으면 바로 댓글싸다구 날려주십쇼!!! 

다음은 또 다른 알고리즘 문제로 찾아 오겠습니다!!

 

즐거운 코딩하시고~ 재밌는 코드 생산하세요!!! 코딩하는 JAY 였습니다~ 아디오스~~:D