[Programmers 코딩 연습] [1차] 추석 트래픽 [Level 3]

문제(출처)-프로그래머스

알고리즘 기법

• Greedy

설명

문제를 푸는 전략은 다음과 같다.

---

처리시간의 시작과 끝을 start_time, end_time이라고 하자.
(end_time = start_time + 1s - 0.001s)
어떤 일의 처리구간을 '막대'라하자. (아래 그림 참조)

(1)의 경우를 보자.
(1)처럼 처리시간을 잡고 몇개의 일을 처리했는지 세는 것은 비효율적이다.
왜냐하면 처리시간의 시작점인 start_time과 첫 번째 막대의 끝점을 맞춰야 더 많은 막대를 처리할 수 있기 때문이다. (아래 그림 참조)

따라서 첫 번째 막대부터 시작해서 마지막 막대까지 각각 막대의 끝점과 start_time을 맞추었을 때 (start_time~end_time)안에 얼마나 많은 막대를 처리 하는지 구하여 그 값들 중 가장 큰 값을 고른다면 답을 구할 수 있다.

---

다음으로 생각해야할 것은 "hh:mm:ss.sss" 문자열을 어떻게 비교하는지에 대해서다.
가장 간단한 방법은 시간, 분, 초, 밀리초를 전부 밀리초 단위로 바꿔서 비교를 하는 것이다.
integer의 범위를 넘어가지 않을까 걱정할 수도 있지만, 24x60x60x1000은 1억이 채 되지 않으니 걱정하지 않아도 된다.
ex) "23:59:18.456" -> ((((23 x 60) + 59) x 60) + 18) x 1000 + 456 -> 86,358,456

소스코드

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

int solution(vector<string> lines) {
    int answer = 0;
    int cnt;
    
    int hour, min, sec, msec;
    int sec_temp, msec_temp;
    int time1, time2;
    
    const int doing_time = 1000;
    int doing_start, doing_end;
    
    int i, j, len;
    
    
    vector<vector<int>> lines_int;
    
    // 문자열을 밀리초 단위의 시간으로 변경해서 저장.
    for (string &line : lines) {
        sscanf(line.c_str(), "2016-09-15 %d:%d:%d.%d %d.%ds", &hour, &min, &sec, &msec, &sec_temp, &msec_temp);
        
        time1 = 60 * hour + min;
        time1 = 60 * time1 + sec;
        time1 = 1000 * time1 + msec;
        
        time2 = 1000 * sec_temp + msec_temp;
        
        lines_int.push_back({time1, time2});
    }
    
    
    //최대 개수 구하기 (doing start, doing_end는 처리시간 T의 시작, 종료 시각)
    for (i = 0, len = lines_int.size(); i < len; i++) {
        doing_start = lines_int[i][0];
        doing_end = doing_start + doing_time - 1;
        cnt = 1;
        for (j = i + 1; j < len; j++) {
            // lines_int[j][0] - lines_int[j][1] 일의 시작 시각
            // lines_int[j]가 처리시간 T (doing_start ~ doing_end) 안에 포함된다면 cnt++
            if (!(lines_int[j][0] - lines_int[j][1] + 1 > doing_end || lines_int[j][0] < doing_start))
                cnt++;
        }
        if (answer < cnt)
            answer = cnt;
    }
    
    return answer;
}

참고

scanf는 standard input, 즉 콘솔로부터 값을 입력 받는 함수고, fscanf는 파일, sscanf는 문자열로부터 값을 입력 받는다.
따라서 "2016-09-15 23:45:18.456"을 정수로 뽑아내려면,
sscanf("2016-09-15 23:45:18.456", "%d:%d:%d.%d", &hour, &min, &sec, &msec); 과 같이 사용하면 쉽게 정수를 추출할 수 있다.