반갑습니다!

[프로그래머스] 추석 트래픽 본문

알고리즘 문제 풀이

[프로그래머스] 추석 트래픽

김덜덜이 2020. 5. 8. 23:34
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr

풀이

모든 시간을 millisec 단위로 변환하여 해결하였다. 문제는 1초간 처리하는 최대 갯수를 구하는 것이다. 입력값을 계산해서 시작 시간과 완료 시간을 구할 수 있는데, millisec로 변환했기 때문에 초 단위의 트래픽 처리량을 체크하기위한 별도의 처리를 해줘야한다.

예를 들어 13시 21분 3.001초에 1초간 트래픽 처리를 시작했다면 13시 21분 3초부터 4초까지 실시했다는 것을 알 수 있다. 이번에는 13시 21분 3.012초에 1초간 트래픽 처리를 했다면 13시 21분 3초부터 13시 21분 5초까지 트래픽 처리가 되었다고 볼 수 있는 것이다. 따라서 처리 끝 시간을 millisec 단위로 바꾸게 되면 999를 더해 범위를 조정해야한다.

millisec로 시작 시간과 완료 시간을 구하게 되면 배열을 통해 처리를 표시하고, 최대값을 구하면 정답을 찾을 수 있다.

코드

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

int chk[60 * 60 * 24 * 1000 + 1];

struct Time {
    int h, m, s, ss;
};

// 처리 시간을 millisec로 변환해주는 함수
int get_millisec(string millisec) {
    int ret = 0;
    if (millisec.find('.') == string::npos) return stoi(millisec.substr(0, 1)) * 1000;
    for (int i = 0; i < millisec.length(); i++)
        if (millisec[i] == '.') {
            ret += stoi(millisec.substr(0, 1)) * 1000;
            ret += stoi(millisec.substr(i + 1));
            break;
        }
    return ret;
}

// 처리가 끝난 시간을 int로 변환해주는 함수
Time parse_lines(string str) {
    int h = stoi(str.substr(11, 2));
    int m = stoi(str.substr(14, 2));
    int s = stoi(str.substr(17, 2));
    int ss = stoi(str.substr(20, 3));
    return { h, m, s, ss };
}

int solution(vector<string> lines) {
    int answer = 0;
    for (string str : lines) {
        // 시간을 millisec 단위로 변경
        Time t = parse_lines(str);
        int h = t.h * 60 * 60 * 1000;
        int m = t.m * 60 * 1000;
        int s = t.s * 1000;
        int ss = t.ss;
        int pt = get_millisec(str.substr(24));

        // 끝나는 시간을 millisec로 구한다
        int last = h + m + s + ss;
        // 시작한 시간을 구한다.
        int first = last - pt + 1;
        // 초 단위 답을 구하기 위해 999를 더해준다
        last += 999;
        // 0보다 작으면 9월 14일이 되므로 9월 15일 00시 00분 00초로 변경
        if (first < 0) first = 0;
        // 최대 범위를 벗어나면 최대값으로 변경
        if (last > 24 * 60 * 60 * 1000) last = 24 * 60 * 60 * 1000;

        // 범위 내 값 증가
        for (int i = first; i <= last; i++)
            chk[i]++;
    }

    for (int i = 0; i <= 24 * 60 * 60 * 1000; i++)
        answer = max(answer, chk[i]);
    return answer;
}

'알고리즘 문제 풀이' 카테고리의 다른 글

[백준] 15683 감시  (0) 2020.05.11
[프로그래머스] 불량 사용자  (0) 2020.05.09
[백준] 14891 톱니바퀴  (0) 2020.05.08
[백준] 14890 경사로  (0) 2020.05.08
[프로그래머스] 셔틀버스  (0) 2020.05.07