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

추석 트래픽

코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

#define HOUR_START 11
#define HOUR_END 12
#define MINUTE_START 14
#define MINUTE_END 15
#define SECOND_START 17
#define SECOND_END 18
#define MS_START 20
#define MS_END 22
#define TIME_START 24
#define MS_PER_HOUR 3600000
#define MS_PER_MINUTE 60000
#define MS_PER_SECOND 1000

using namespace std;

int responseTimeToMS(const string& str) {
    int h, m, s, ms;
    int total = 0;

    h = m = s = ms = 0;

    for (int i = HOUR_START; i <= HOUR_END; i++)
        h = (h * 10) + (str[i] - '0');
    for (int i = MINUTE_START; i <= MINUTE_END; i++)
        m = (m * 10) + (str[i] - '0');
    for (int i = SECOND_START; i <= SECOND_END; i++)
        s = (s * 10) + (str[i] - '0');
    for (int i = MS_START; i <= MS_END; i++)
        ms = (ms * 10) + (str[i] - '0');

    h *= MS_PER_HOUR;
    m *= MS_PER_MINUTE;
    s *= MS_PER_SECOND;

    total = h + m + s + ms;

    return total;
}

int processTimeToMS(const string& str) {
    int s = 0;
    int ms = 0;
    int length = str.length();
    size_t pointIdx = str.find('.');

    if (pointIdx != string::npos) {
        for (int i = 0; i < pointIdx; i++)
            s = (s * 10) + (str[i] - '0');
        for (int i = pointIdx + 1; i < length - 1; i++)
            ms = (ms * 10) + (str[i] - '0');
    } else {
        for (int i = 0; i < length - 1; i++)
            s = (s * 10) + (str[i] - '0');
    }

    return s * 1000 + ms - 1;
}

int solution(vector<string> lines) {
    int answer = 1;
    int start, end, ps;
    int size = lines.size();
    vector<pair<int, int>> times;
    priority_queue<int> pq;

    for (int i = 0; i < lines.size(); i++) {
        end = responseTimeToMS(lines[i]);
        start = end - processTimeToMS(lines[i].substr(TIME_START));

        times.push_back(make_pair(start, end));
    }

    sort(times.begin(), times.end());

    pq.push(-times[0].second);
    for (int i = 1; i < size; i++) {
        while (!pq.empty() && ((-pq.top()) + 999 < times[i].first)) {
            pq.pop();
        }
        pq.push(-times[i].second);
        if (answer < pq.size()) answer = pq.size();
    }

    return answer;
}

풀이

• 가장 빨리 종료되는 시간을 받아오기 위한 priority_queue 선언
• 종료 시간을 ms 단위로 변환 후 시작 시간을 계산하여 함께 times 배열에 추가
• times 배열을 시작 시간 오름차순 정렬
• priority_queue에 tiems의 첫번째 원소의 종료시간을 push (STL에서 제공하는 priority_queue는 최댓값이 top에 있기 때문에 최솟값을 top에 두기 위하여 마이너스 연산을 하여 push)
• i를 1 ~ (size - 1)까지 1씩 증가시키며 반복문 수행
• priority_queue의 top + 999 보다 i번째 원소의 시작 시간이 더 클 동안 priority_queue의 pop을 호출
• priority_queue에 i번째 원소의 종료 시간을 push
• priority_queue의 size가 answer보다 클 경우 answer에 priority_queue의 size 저장

다른 방법

• https://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/