카카오/코딩테스트 기출/추석트래픽/2018 Blind Recruitment 1차/cpp(C++)풀이

cpp(C++)로 풀었으니 참고. 

카카오 기출을 한 번 풀어야겠다고 마음 먹고 처음 접한 문제다. 그냥 이름 재밌어보이는거로 잡았는데 하필이면 난이도: 상 짜리.. 눈물나게 고민하고 풀었다. 하루종일 생각했다. 솔직히 처음에 감이 안잡혀서 카카오 공식 홈페이지에 해설을 간단하게 읽어본 후 많은 고민 끝에 구현할 수 있었다.. (그러니까 후딱 안풀린다고 절대 좌절하지 말자!)

크게 아래와 같은 로직으로 생각했다. 

1. 대전제로 먼저 모든 시간은 millisecond 단위로 변환하자. 그렇다고 해도 int 범위안에 넉넉하게 담을 수 있으니 ok
2. 각 로그 문자열마다 순회를 하면서 먼저 string을 시간으로 변환한다. 아래는 각 로그 문자열string처리 로직이다.
   • 로그 문자열의 종료 시간(endTime)을 먼저 millisecond로 환산해서 구한다.
   • 로그 문자열의 시작 시간(startTime)을 구한다. 앞서 구한 종료 시간(endTime)과 파싱한 경과 시간(elapsedTime)을 이용하여 구할 수 있다.
3. 위에서 처리한 문자열을 pair<int, int>에 <시작 시간(startTime), 종료 시간(endTime)> 순으로 저장하자. 
4. 이제 이 pair를 순회하면서 각 pair 마다 (종료 시간 - 1ms) ~ (종료 시간 -1ms + 1000ms(1초)) 기준 구간을 잡아 준 후, 모든 pair의 각 기준 구간에 대해 모든 pair들을 순회하면서 그 기준 범위 안에 들어가있는지 카운트 해준다. 즉, 시간 복잡도는 로그 문자열의 길이가 N이라면 O(N^2) 을 갖게 될 것이다. 
5. 이렇게 구한 카운트의 최대값을 출력해주면 정답이 된다. 

내 생각에 여기서의 포인트는 4번이다. 1초 범위로 스냅샷을 찍었을 때 가장 처리가 많이 되고 있는 구간을 찾는 문제인데, 그 스냅샷을 찍는 범위를 어떻게 할지가 관건이라고 생각한다. 1ms 로 이동하면서 1초 범위를 계속 잡는다면 24시간동안 1ms * 1000 * 60 * 60 * 24 = 86,200,000 가지의 범위에 대해 모두 계산을 해야 하므로 비효율적이다. 따라서 각 로그 문자열의 종료 시간을 기준으로 거기보다 1ms 적은 값을 시작시간으로 해두고 1초 간의 범위를 생각하면, 86,200,000개가 아닌 로그 문자열의 개수만큼의 범위만 고려하면 되는 것이다. 범위를 막대로 직접 그리면서 생각하다 보면 이해가 갈 것이다. 

#include <string>
#include <vector>

using namespace std;
int getStartTime(int &endTime, string &line){
    int startTime = 0;
    string tmp = line.substr(24); tmp.pop_back();
    int elapsedTime = stod(tmp.c_str())*1000;
    startTime = endTime - elapsedTime + 1;
    return startTime;
}

int getEndTime(string &tmp){
    int endTime = 0;
    int hours = atoi(tmp.substr(0,2).c_str())*60*60*1000;
    int minutes = atoi(tmp.substr(3,2).c_str())*60*1000;
    int seconds = atoi(tmp.substr(6,2).c_str())*1000;
    int milliseconds = atoi(tmp.substr(9,3).c_str());
    endTime = hours + minutes + seconds + milliseconds;
    return endTime;
}

vector<pair<int,int>> timeParse(vector<string> &lines){
    vector<pair<int,int>> times;
    for(int i = 0; i < lines.size(); ++i){
        string tmp = lines[i].substr(11,12);
        int endTime = getEndTime(tmp);
        int startTime = getStartTime(endTime, lines[i]);
        times.push_back(make_pair(startTime, endTime));
    }
    return times;
}

int solution(vector<string> lines) {
    int answer = 0;
    vector<pair<int,int>> times = timeParse(lines);
    for(int i = 0; i < times.size(); i++){
        int rangeStart = times[i].second - 1;
        int rangeEnd = rangeStart + 1000;
        int count = 0;
        for(int j = 0; j < times.size(); ++j){
            if(times[j].first <= rangeEnd && times[j].second >= rangeStart){
                count++;
            }
        }
        if(count > answer) answer = count;
    }
    return answer;
}

source code: https://github.com/brwnsugr/algorithm/blob/master/kakao_test/2018_1st_thanksgiving_traffic.cpp