[C++로 풀이] 추석 트래픽 (문자열 파싱, 실수 처리)⭐⭐⭐

Date: 2021.03.07 Updated: 2021.03.07

카테고리: Programmers

📌 추석 트래픽

난이도 ⭐⭐⭐

🚀 문제

“2016-09-15” 는 고정이다.

🚀 내 풀이 ⭕

#include <string>
#include <sstream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<string> lines) {
    int answer = 0;
    int n = lines.size(); // 로그 개수
    vector<int> start(n); // start[i] : i + 1 번째 로그의 "시작시간"
    vector<int> end(n);   // end[i] : i + 1 번째 로그의 "종료시간"
    vector<int> perSeconds; // 초당 처리량 (빈 벡터)

    /* 문자열 파싱 */
    int hours, minutes, seconds, workTime = 0;
    string s, t;
    for (int i = 0; i < n; ++i) {
        istringstream iss(lines[i].substr(11));
        iss >> s >> t;

        hours = stoi(s.substr(0, 2)) * 1000;
        minutes = stoi(s.substr(3, 2)) * 1000;
        seconds = stoi(s.substr(6, 2)) * 1000 + stoi(s.substr(9, 3));
        t.pop_back();
        workTime += stoi(t.substr(0, 1)) * 1000;
        if (t.length() >= 3)
            workTime += stoi(t.substr(2));

        end[i] = 3600 * hours + 60 * minutes + seconds;
        start[i] = end[i] - workTime + 1;
        workTime = 0;
    }
    
    /* 초당 처리량 구하기 */
    // 첫번째 로그의 시작 시간으로부터의 1 초 동안의 처리량 (이 1 초 구간에 속하는 로그들 카운팅)
    int count = 0;
    for (int i = 0; i < n; ++i) 
        if (start[i] < start[0] + 1000)
            count++;
    perSeconds.push_back(count);
    // 모든 로그들의 종료 시간으로부터 1 초 동안의 처리량 (이 1 초 구간에 속하는 로그들 카운팅)
    count = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (end[i] <= end[j])
                if (start[j] < end[i] + 1000)
                    count++;
        }
        perSeconds.push_back(count);
        count = 0;
    }

    answer = *max_element(perSeconds.begin(), perSeconds.end()); // 초당 처리량을 모아둔 perSeconds 에서 최대값을 찾으면 그게 바로 답! (초당 최대 처리량)
    return answer;
}

🔥 로그 문자열 파싱하여 시작시간, 종료시간 구하기

우선 하나하나의 처리(로그)들 각각의 시작 시간과 종료 시간을 구해야할 필요가 있다. 초당 처리량을 구하는데 시작 시간과 종료 시간으로 해당 로그가 어떤 ‘1초 구간’에 속하는지 판별할 것 이기 때문이다.

        istringstream iss(lines[i].substr(11)); // 12번째 글자부터 끝까지 서브 문자열
        iss >> s >> t; // 공백(띄어쓰기)을 기준으로 파싱되어 들어감

“03:10:33.020 0.011s” 👉 12번째 글자 ~ 끝까지 (“2016-09-15 “은 늘 고정이다. 11 글자!)
- s : 응답 완료 시간
  - “03:10:33.020”
- t : 처리 시간
  - “0.011s”

        hours = stoi(s.substr(0, 2)) * 1000; // s[0] ~ s[1] 이렇게 2글자는 시간
        minutes = stoi(s.substr(3, 2)) * 1000; // s[3] ~ s[4] 이렇게 2글자는 분
        seconds = stoi(s.substr(6, 2)) * 1000 + stoi(s.substr(9, 3)); // s[6] ~ s[7] 이렇게 2글자는 정수 초, 점을 제외한 그 뒤의 s[9] ~ s[11] 3글자는 초의 3 자리의 소수

s 응답완료시간 파싱

비교가 쉽도록 s 응답 완료 시간을 “초”로 바꾸기 위해 시간, 분, 초로 나눈다.

1000을 곱해준 이유
- 👉 실수는 비교가 정확하지 않기 때문에 정수로 변환한 상태에서 비교하기 위해서다. 문제에선 소수 셋째 짜리까지만 따지기 때문에 일괄적으로 1000을 곱하여 소수점을 모두 없앴다.
  - 처음엔 stof 함수를 사용하여 “33.020” 를 소수 그대로로 변환하여 float 타입의 33.020 로 사용하려고 했었다. 컴퓨터는 부동소수점 방식으로 실수를 표현하기 때문에 완전히 정확하지 않다. 딱떨어지게 33.020 이 되지 못할 수도 있다.(예를들어 33.020934893489 일 수 있음) 그래서 “33.020” 같은 것을 stof을 통해 float으로 변환시키면 33.020 가 아닌, 소수점 뒤의 자리들로 인하여 반올림되어 33.021 가 될 수도 있었다.
  - 또한 어차피 컴퓨터가 표현하는 실수는 부동소수점이므로 33.020 자체도 정확한 33.020 이 아니기 때문에 실수끼리의 크기 비교 또한 완전히 정확하지 못하다.(그래서 오차를 설정해 주어야 하는 귀찮음이 따른다.) 그래서 정수로 변환한 것!
ex) “03:10:33.020”
- hours : 3000
- minutes : 10000
- seconds : 33020

        t.pop_back(); // 뒤에 s 뗌
        workTime += stoi(t.substr(0, 1)) * 1000;  // 정수 초 1글자
        if (t.length() >= 3)
            workTime += stoi(t.substr(2)); // 인덱스2부터 끝까지 (끝에 s는 뗐으니까 괜춘)

t 처리시간 파싱 ex) “0.011s”, “2s”, “2.0s”

뒤에 s는 뗀다.
처리시간의 ‘초’의 정수
- 처리시간의 최대 시간은 3초이기 때문에 어차피 한 자리 밖에 안된다.
처리시간의 ‘초’ 소수점
- “2” 이런식으로 정수만 들어가는 초는 1글자지만 “2.0” 이렇게 소수점이 붙는 형태면 3 글자 이상이다. 처리시간 문자열의 길이가 3 글자 이상이라면 소수가 붙어있다는 것이므로 파싱해야 한다.
- 인덱스2 (3번째 글자니까 . 다음 글자)부터 끝까지를 떼오면 된다.
ex) “0.011s”
- workTime : 11
ex) “2s”
- workTime : 2000

        end[i] = 3600 * hours + 60 * minutes + seconds;
        start[i] = end[i] - workTime + 1;
        workTime = 0; // 다음 반복때 또 써먹어야해서 0으로 초기화 (+= 사용해서 0 으로 초기화 해줘야함)

종료 시간
- 그냥 s 응답 완료 시간에서 구한 hours, minutes, seconds 를 통합하여 ‘초’로 대입하면 됨
- ex) “03:10:33.020”
  - end[i] = 3600 * 3000 + 60 * 100000 + 33020 = 11433020
시작 시간
- 문제 조건에 의하면 처리 시간은 시작 시간과 종료 시간을 모두 포함한다.
- 시작 시간 = 종료시간 - 처리시간 + 1
  - 사실 0.001초 더해주는거나 마찬가지인데 현재 1000 을 곱해 다 정수로 변환한 상태이니 +1 이 되는 것.

lines 로그들은 시간 순서대로 정렬되어서 주어졌기 때문에(응답 완료 시간을 기준으로 오름차순 정렬) 순서대로 lines 로그들의 시작 시간과 종료 시간을 구했기에 결론적으로 start와 end도 시간 순서대로 정렬이 되어 있는 모습이 된다.

🔥 초당 처리량 구하기 (1초 동안의 처리량)

구간의 시작과 끝이 로그의 시작 시간과 종료 시간과 겹치더라도 구간에 속하는 것으로 간주한다.

초당 "최대" 처리량을 구하는 것이 목적이고, 또한 시작점과 끝점이 처리 시간에 포함되기 때문에 0.001 초 단위로 매번 검사하기 보다는, 로그들 각각의 종료 시간마다 (종료시간도 포함되니까) 그 종료 시간으로부터 1 초 동안에 속한 로그들을 카운팅하면 된다. 최대한 많은 처리량이 등장한 1 초 구간을 찾기 위해서!! 시작 시간으로부터 1 초 구간에 속하는지로 초당 처리량을 구하는건 최대한 1초 동안의 많은 처리량을 구하려는데 적합하지 않다고 판단한 이유는 조금만 더 가도 새로운 로그가 등장할 수 있기 때문에 애초에 최대 처리량을 구하고자 하는 목적에 부합하지 않기 때문이다.

✔ 한번, 첫 번째 로그의 시작 지점에서부터 1 초 구간에 속하는 로그들 카운팅
- 1️⃣ 로그들의 시작점이 [첫 번째 로그의 시작 지점에서부터 1 초 구간] 의 “끝점”(start[0] + 1000)보다 더 앞에 있는지를 따진다. (크기가 더 작은지)
✔ 모든 로그들의 종료 지점에서부터 1 초 구간에 속하는 로그들 카운팅
- 1️⃣ 로그들의 시작점(start[j])이 [해당 로그의 종료 지점에서부터 1 초 구간] 의 “끝점”(end[i] + 1000)보다 더 앞에 있는지를 따진다. (크기가 더 작은지)
- 2️⃣ 로그들의 끝점(end[j])이 [해당 로그의 종료 지점에서부터 1 초 구간] 의 “시작점”(end[i])보다 더 뒤에 있는지를 따진다. (크기가 더 큰지)
- 위 1️⃣2️⃣ 가 동시에 만족해야 한다.

    // 첫번째 로그의 시작 시간으로부터의 1 초 동안의 처리량 (이 1 초 구간에 속하는 로그들 카운팅)
    int count = 0;
    for (int i = 0; i < n; ++i) 
        if (start[i] < start[0] + 1000)
            count++;
    perSeconds.push_back(count);

첫 번째 로그의 시작 지점에서부터 1 초 구간에 속하는 로그들 카운팅. 초록색은 첫번째 로그, 노란색은 구간에 속하는 로그들 (즉, 1초 동안의 처리량에 속할 수 있는지) 회색은 구간에 속하지 않는 로그들이다.

해당 1 초 구간에 속하는 로그들은 총 3 개

    // 모든 로그들의 종료 시간으로부터 1 초 동안의 처리량 (이 1 초 구간에 속하는 로그들 카운팅)
    count = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (end[i] <= end[j])
                if (start[j] < end[i] + 1000)
                    count++;
        }
        perSeconds.push_back(count);
        count = 0;
    }

모든 로그들의 종료 지점에서부터 1 초 구간에 속하는 로그들 카운팅

해당 1 초 구간에 속하는 로그들은 총 4 개 (두 경우 다)

🔥 초당 최대 처리량 구하기

answer = *max_element(perSeconds.begin(), perSeconds.end());

초당 처리량을 모아둔 perSeconds 에서 최대값을 찾으면 그게 바로 답! (초당 최대 처리량)

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

공부하는 식빵맘 👱‍♀️