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

이 문제는 완전 탐색으로 풀 수 있다.

 

이 문제를 정말 그대로 구현하면 24 * 60 * 60 * 1000 * 1000 = 86,400,000,000 번의 연산이 필요하여 시간 초과가 난다.

로그 배열의 최대 크기는 2,000 이므로, O(N^2) 이하의 알고리즘을 구현하면 시간 초과가 나지 않는다.

 

그래서 각 로그에 대해 루프를 돌면서 다른 로그들을 순회하는 방식의 알고리즘을 생각했다. 1초의 인터벌을 가지는 구간은 총 4개가 나올 수 있는데, start 왼쪽, start 오른쪽, end 왼쪽, end 오른쪽 이다. 그래서 각 로그마다 해당 4개의 구간을 설정하여 다른 로그들이 이 안에 들어올 경우 각각에 대해 1을 더해주고, 마지막에 네 개 중 가장 개수가 많은 것을 저장하는 방식으로 정답을 맞출 수 있었다.

#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <utility>
using namespace std;

#define INTERVAL 999

vector<pair<int, int>> times;

vector<string> split(string input, char delimiter)
{
    stringstream ss(input);
    vector<string> result;
    string temp;
    while (getline(ss, temp, delimiter))
    {
        result.push_back(temp);
    }
    return result;
}

bool isInside(int originStart, int originEnd, int start, int end)
{
    if (end < originStart || originEnd < start)
    {
        return false;
    }
    return true;
}

int solution(vector<string> lines) 
{
    for (string line : lines)
    {
        vector<string> space = split(line, ' ');
        vector<string> hmsm = split(space[1], ':');
        vector<string> sm = split(hmsm[2], '.');
        int hour = stoi(hmsm[0]) * 60 * 60 * 1000;
        int minute = stoi(hmsm[1]) * 60 * 1000;
        int second = stoi(sm[0]) * 1000;
        int millie = stoi(sm[1]);
        double tDouble = stod(space[2].substr(0, space[2].size() - 1));
        int t = (int)(tDouble * 1000);
        int startTime = hour + minute + second + millie - (t - 1);
        int endTime = hour + minute + second + millie;
        times.push_back({startTime, endTime});
    }
    int answer = 1;
    for (int i = 0; i < times.size(); i++)
    {
        int presentStart = times[i].first;
        int presentEnd = times[i].second;
        int leftStart = 1;
        int startRight = 1;
        int leftEnd = 1;
        int endRight = 1;
        int temp = 0;
        for (int j = 0; j < times.size(); j++)
        {
            if (i == j)
            {
                continue;
            }
            int tempStart = times[j].first;
            int tempEnd = times[j].second;
            // 1. left start
            if (isInside(presentStart - INTERVAL, presentStart, tempStart, tempEnd))
            {
                leftStart++;
            }
            // 2. start right
            if (isInside(presentStart, presentStart + INTERVAL, tempStart, tempEnd))
            {
                startRight++;
            }
            // 3. left end
            if (isInside(presentEnd - INTERVAL, presentEnd, tempStart, tempEnd))
            {
                leftEnd++;
            }
            // 4. end right
            if (isInside(presentEnd, presentEnd + INTERVAL, tempStart, tempEnd))
            {
                endRight++;
            }
        }
        temp = max(max(leftStart, startRight), max(leftEnd, endRight));
        answer = max(answer, temp);
    }
    return answer;
}