[ 프로그래머스 [1차] 추석 트래픽 (Lv3) ] (C++)

프로그래머스의 추석 트래픽(Lv3) 문제이다.

[ 문제풀이 ]

문제를 본격적으로 풀이보기 전에 주어진 정보들을 어떻게 이용하고, 어떻게 변환해야 하는지부터 순차적으로 단계별로 진행해보자.

# 응답 완료 시간 (hh : mm : ss . sss)

이 문제에서 입력으로 주어지는 문자열 중에서, 날짜를 표현하는 부분은 신경을 쓰지 않아도 된다.

그럼 시간을 어떻게 나타낼지를 알아보자.

입력형식에 보면 "응답완료시간 S는 hh:mm:ss.sss" 라고 되어있다.

우리는 이 부분에서 마지막에 .sss가 붙는 것으로 보아, 소수점 셋째자리 까지 표현된다는 것을 알 수 있다.

즉, 시간이 ms단위까지 표시된다고 생각할 수 있다.

그리고 당연하게도, 초가 60을 넘어서면 분이 증가하고, 분이 60을 넘어서면 시가 증가하게 된다.

문제는 이런 복잡한 관계들을 주어진 형태로만 구분하기는 쉽지 않다는 것이다.

따라서, 본인은 모든 시간을 ms 단위로 변환해 주었다.

시(hh)같은 경우에는 K 시라는 값이 주어졌다고 가정해보면, K시를 분으로 표현하면, K * 60이 되고,

이를 초로 표현하게 되면 K * 60 * 60 이 되고, 여기서 ms단위로 표현하기 위해서는 K * 60 * 60 * 1000이 된다.

분(mm) 같은 경우에는 K 분이라는 값이 주어졌다고 가정해보면, 이를 ms단위로 표현하기 위해서는

K * 60 * 1000이 된다.

초(ss)같은 경우에는 K * 60이 된다.

즉, 응답완료시간으로 [ hh : mm : ss . sss ] 가 주어졌다고 가정했을 때, 이 시간을 ms로 변환하게 되면,

응답완료시간(ms) = (hh * 60 * 60 * 1000) + (mm * 60 * 1000) + (ss * 1000) + sss 가 된다.

그래서 이렇게 주어진 문자열을 int형으로 변환 후, 위와 같은 ms단위로 변환하는 과정을 가장 먼저 진행해 주었다.

# 처리 시간

처리 시간 같은 경우에는 최대 소수점 셋째 짜리 까지 주어질 수 있으니, 그 단위는 's'로 주어진다고 되어있다.

즉 ! 우리는 기존에 응답완료시간을 ms단위로 변환하였는데, 처리시간은 s로 주어진다는 것이다.

따라서, 본인은 이 처리시간 또한 ms로 변환해 주었다.

변환해 주기 위해서는, 주어진 처리시간 * 1000을 하면 ms 단위로 변환한 꼴이 된다.

# 응답완료시간과 처리시간간의 관계

1. 트래픽을 처리하기 시작한 시간

우리가 위에서 진행했던 것과 같이, ms단위로 모두 변환했을 때 우리에게 주어진 응답완료시간을 'A(ms)' , 처리시간을 B(ms) 라고 가정해보자.

그럼 우리가 해당 트래픽을 처리하기 시작한 시간은 몇ms가 될까 ??

바로, A - B + 1 ms가 된다. 주어진 입력 형식을 보면 알 수 있는 부분인데, 33.020 에서 응답완료된 트래픽의 처리시간이 0.011s 라고 주어졌다면, 이는 33.010 부터 33.020 까지 진행되었다고 적혀있다.

즉, 트래픽을 처리하기 시작한 시간 = [ 응답완료시간 - 처리시간 + 1 ] 이 된다.

2. 트래픽을 처리한 마지막 시간

그럼, 트래픽을 처리한 마지막 시간은 어떻게 계산할 수 있을까 ??

얼핏보면, 계산이 필요하지 않다. 왜냐하면 우리는 지금까지 계속해서 "응답완료시간" 에 대해서 계산을 했기 때문이다.

그래서 본인도 처음에는 "응답완료시간이 트래픽을 처리한 마지막 시간" 이라고 생각을 했었다.

그런데 ! 예제입력2번을 한번 보자.

첫 번째 로그는 02.003 ~ 04.002 에서 처리되었고, 두 번째 로그는 05:001 ~ 07:000 에서 처리되었다고 되어있다.

즉 ! 2개의 로그의 처리 시간이 서로 겹치지 않기 때문에, 동시에 처리하는 것이 불가능해 보이지만, 우리가 구하고자 하는 것은

"1초(=1,000밀리초)간 처리하는 요청의 최대갯수" 이다.

즉 ! 04.002 초부터 1초를 Count한다고 가정해보면, 위의 2개의 로그를 동시에 처리할 수 있다.

즉 ! 1초간 처리할 수 있는 로그의 갯수가 2개가 가능하다는 것이다.

그래서, 본인은 "위의 2개의 로그가, 마치 겹친 것 처럼 보이게 표현" 해주기 위해서 트래픽을 처리한 마지막 시간에 + 999초를 해 주었다. 999초를 더한 것은, 처리시간은 시작시간과 끝시간을 포함하기 때문에, 1000을 더해버린다면, 1001초가 더해버린 것과 같은 효과가 되어버리기 때문이다.

즉, 트래픽을 처리한 마지막 시간 = [ 응답완료시간 + 999 ] 가 된다.

# 초당 트래픽 최대 처리 횟수 구하기

우리는 위의 과정을 통해서, 각 로그들의 '처리 시작 시간', '처리 완료시간' 을 모두 구했다.

그리고 본인은 위의 시간을 모두 vector에 넣어주었다.

즉, 하나의 로그당 2개의 값이 vector에 삽입이 된다. '처리 시작시간' 과 , '처리완료 시간' 2개의 값이 !

그리고 또 하나 표시를 해주었다. 삽입된 시간이 처리 시작을 의미하는지, 처리 완료된 시간을 의미하는지 !

즉, vector는 vector<pair<int, bool>> 형태로 선언해주었고, 로그가 처리 시작시간을 'Start', 로그가 처리 완료된 시간을 'End'라고 가정해보면, vector에는 pair(Start, true), pair(End, false) 이런식으로 한 로그당 2개의 값들을 vector에 넣어주었다.

그리고 나서 해당 vector를 시간순으로 오름차순으로 정렬을 해 주었다.

오름차순으로 정렬하게 되면 어떤 상황이 발생하게 될까 ??

바로, "동시에 처리할 수 있는 로그의 갯수"를 파악할 수 있게 된다.

예를 들어서 다음과 같은 상황이 있다고 가정해보자.

[ 처리 시작 시간 , 처리 완료 시간 ] 으로 표현했을 때,

로그1 : [ 2000 , 2010 ]

로그2 : [ 2005 , 2020 ]

로그3 : [ 2032 , 2045 ]

라는 상황이 있다고 가정해보자.

이를 vector에 넣은 후, 정렬을 했다면 vector는 다음과 같은 상태일 것이다.

[ (2000, true) , (2005, true) , (2010 , false) , (2020 , false) , (2032 , true) , (2045 , false) ] 가 될 것이다.

그럼 ? 우리는 vector를 순차적으로 탐색하면서 나오는 로그의 상태가 'true'라면 처리갯수를 ++, 그게 아니라면 --를 하면서 진행한다면, 초당 처리할 수 있는 최대 갯수를 알 수 있다.

위의 예시에 대해서 말해보자면, (2000 , true) 에서 처리할 수 있는 갯수 = 1개

(2005 , true) 에서 처리할 수 있는 갯수 = 2개

(2010 , false) 에서 처리할 수 있는 갯수 = 1개

(2020 , false) 에서 처리할 수 있는 갯수 = 0개

(2032 , true) 에서 처리할 수 있는 갯수 = 1개

(2045 , false) 에서 처리할 수 있는 갯수 = 0개

로써, 동시에 처리할 수 있는 최대 갯수는 2개가 된다.

[ 소스코드 ]

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
// h = 11 , 12
// m = 14 , 15
// s = 17 , 18 
// ms = 20 , 21 , 22
 
int Invert_Time(vector<int> Idx_V, int line_Idx, vector<string> line)
{
    /* 응돱완료 시간을 ms로 변환하는 과정. */
    string Result = "";
    int Idx = 0;
    for (int i = 0; i < Idx_V.size(); i++) Result = Result + line[line_Idx][Idx_V[i]];
    return stoi(Result);
}
 
int Invert_Response_Time(int line_Idx, vector<string> line)
{
    /* 처리시간을 ms로 변환하는 과정. */
    /* ms로 표현 한다는 것 = 결과적으로 4자리 숫자가 나와야 함. 1s = 1000ms */
    /* 따라서, string형으로 표현한 처리시간을, 4자리 문자열로 만든 후 int형으로 변환 */
    string Result = "";
    int Idx = 24;
    while (line[line_Idx][Idx] != 's')
    {
        if (line[line_Idx][Idx] == '.')
        {
            Idx++;
            continue;
        }
        Result = Result + line[line_Idx][Idx++];
    }
    while (Result.length() != 4) Result = Result + '0';
    return stoi(Result);
}
 
bool Cmp(pair<int, bool> A, pair<int, bool> B)
{
    if (A.first <= B.first)
    {
        if (A.first == B.first)
        {
            if (A.second > B.second)
            {
                return true;
            }
            return false;
        }
        return true;
    }
    return false;
}
 
int solution(vector<string> lines) 
{
    vector<string> My_lines = lines;
    vector<pair<int, bool>> Time;
    for (int i = 0; i < My_lines.size(); i++)
    {
        int H = Invert_Time({ 11, 12 }, i, My_lines);
        int M = Invert_Time({ 14, 15 }, i, My_lines);
        int S = Invert_Time({ 17, 18 }, i, My_lines);
        int Ms = Invert_Time({ 20, 21, 22 }, i, My_lines);
        int Response_Time = Invert_Response_Time(i, My_lines);
        H = H * 60 * 60 * 1000;
        M = M * 60 * 1000;
        S = S * 1000;
        int Total_Time = H + M + S + Ms;
        int Start_Time = Total_Time - Response_Time + 1;
        int End_Time = Total_Time + 999;
        
        Time.push_back(make_pair(Start_Time, true));
        Time.push_back(make_pair(End_Time, false));
    }
    sort(Time.begin(), Time.end(), Cmp);
    int Traffic = 0;
    int answer = 0;
 
    for (int i = 0; i < Time.size(); i++)
    {
        if (Time[i].second == true) Traffic++;
        else Traffic--;
        
        if (answer < Traffic) answer = Traffic;
    }
    return answer;
}