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

문제링크

---

풀이

지문만 읽어보면 이해가 잘 되지 않지만 예제에 대한 설명이 친절하게 되어있다. 심지어 마지막 설명의 그림은 문제의 풀이에 가깝다.

문제를 보면 각 log는 시작시점과 종료시점이 있다는 것을 알 수 있고, 목표는 1초 동안 최대한 많은 log가 걸치게 하는 것이다.

위 그림의 (1), (2), (3)은 각각 1초의 시간이다. (2)의 1초동안은 7개의 log가 걸치며 이는 최댓값이다.

타임라인에서 모든 순간에 1초동안을 확인하며 몇 개의 로그가 걸치는지 확인하면 쉽게 답을 낼 수 있지만, 이 문제는 시간을 1000분의 1초까지 세기 때문에 모든 순간을 확인하려면 86,400,000번 연산을 해야한다. 굳이 계산해보지 않아도 직관적으로 비효율적이라는 것을 느낄 수 있었다.

더 효율적인 방법으로는 각 로그의 종료시점에 1초를 시작하여 몇개의 로그가 있는지 확인한다면 똑같이 최댓값을 구할 수 있다.

위와 같이 로그 A의 종료시점에서 1초동안 몇개의 로그가 걸치는지 확인한다면 3개의 로그가 걸친다.

하지만 A의 중간에서 1초를 센다면 C까지 미치지 못하고 2개의 로그가 걸치게 된다.

그러므로 1초를 셀 때 각 로그의 종료시점에서 확인해보자

그럼 각 로그가 1초에 걸친다는 건 어떻게 판별할 수 있을까.

1. 1초의 종료시점보다 로그의 시작시점이 앞서면 1초 안에 로그가 들어온다고 판별한다.
2. 하지만 1초의 시작시점보다 로그의 종료시점이 앞선다면 로그가 걸친것으로 판별하면 안된다.

2번 규칙은 조건문을 통해 판별할 수도 있겠지만 로그의 종료시점을 오름차순으로 정렬해준다면 이중반복문의 인덱스를 잘 설정해주는 것으로 조건을 만족할 수 있다.

---

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

using namespace std;

int getTime(string input)
{
    int ret = 0;
    
    ret += stoi(input.substr(11, 2)) * 3600000;
    ret += stoi(input.substr(14, 2)) * 60000;
    ret += stoi(input.substr(17, 2)) * 1000;
    ret += stoi(input.substr(20, 3));
    
    return ret;
}

int getT(string input)
{
    int ret = 0;
    
    ret += (int)(input[24] - '0') * 1000;
    
    if (input.length() > 26)
        ret += stoi(input.substr(26));
    
    return ret;
}

bool cmp(const pair<int, int> &a, const pair<int, int> &b)
{
    return a.second < b.second;
}

int solution(vector<string> lines)
{
    vector<pair<int, int>> log;
    
    for (int i = 0; i < lines.size(); ++i)
    {
        int endtime = getTime(lines[i]);
        log.push_back({endtime - getT(lines[i]) + 1, endtime});
    }
    
    sort(log.begin(), log.end(), cmp);
    
    int ans = 0;
    for (int i = 0; i < log.size(); ++i)
    {
        int t = log[i].second + 999;
        int count = 1;
        
        for (int j = i + 1; j < log.size(); ++j)
        {
            if (log[j].first <= t)
                ++count;
        }
        
        ans = max(ans, count);
    }
    
    return ans;
}

1000분의1초를 숫자1로 카운트하여 int자료형으로 저장해주었다.

각 로그의 시작과 끝을 std::vector< pair<int, int> >로 저장해주었다.