[Algorithm] Programmers :: 추석트래픽

https://school.programmers.co.kr/learn/courses/30/lessons/17676?language=cpp 

프로그래머스

int solution(vector<string> lines) {
    int answer = 0;
 
    vector<int> startV;
    vector<int> endV;
 
    for (int i = 0; i < lines.size(); i++)
    {
        string sh, sm, ss, sms;
        int ih, im, is, process;
 
        lines[i].pop_back();
        sh = lines[i].substr(11, 2);
        sm = lines[i].substr(14, 2);
        ss = lines[i].substr(17, 2);
        sms = lines[i].substr(20, 3);
        int workTime = stof(lines[i].substr(24, 5)) * 1000;
 
        ih = stoi(sh) * 3600 * 1000;
        im = stoi(sm) * 60 * 1000;
        is = stoi(ss) * 1000 + stoi(sms);
 
        int endTime = ih + im + is;
 
        startV.push_back(endTime - workTime + 1);
        endV.push_back(endTime);
    }
 
    for (int i = 0; i < lines.size(); i++)
    {
        int endTime = endV[i] + 1000;
        int count = 0;
 
        for (int j = i; j < lines.size(); j++)
        {
            if (startV[j] < endTime)
            {
                count++;
            }
        }
 
        if (count >= answer) answer = count;
    }
 
    return answer;
}

카카오 3레벨짜리 문제다. 솔직히 오래 걸렸다. 그리고 그만큼 문제를 접해봐서 다행이라는 생각이 들었다.

코드만보면 굉장히 쉬워보이는 문제다. 근데 문제이해가 생각보다 잘 안돼서 오래 걸렸다.

일단 전처리할 때, 캐스팅하는 과정에서 소수점값들이 조금씩 차이가 나서 조금 먼 길을 돌아서 갔다.

그래서 그나마 깔끔한 다른 분의 코드를 참고했다. 이번 문제같은경우는 인풋값의 문자열이 거의 고정값이라 substr로 고정으로 잘라서 변환해도 된다. substr함수같은 경우 시작인덱스 기준으로 몇개나 잘라올건지.. 에 대한건데

몇개에 대해 숫자를 입력할 때 문자열크기를 벗어나더라도 알아서 끝까지만 딱 잘라준다.

그래서 위와같이 코드짜는게 가능하다. 

 

어쨋든 전처리는 어떻게든 할 수 있고, 문제는 카운팅을 무슨 기준으로 하느냐인데.. 의외로 굉장히 심플하다.

오히려 문제의 예제그림때문에 더 어렵게 느껴지고 헷갈릴 수 있는데, 예전에 풀었던 단속카메라 문제랑 상당히 비슷한 문제다. 체크하려는 구간을 잘 설정해야하는 문제인데..

안그래도 보자마자 약간 그 문제랑 비슷한 느낌이 왔었는데, 거기서 더 생각을 못해버렸다;;

 

일단 기본적으로 인풋벡터는 작업의 종료시간 기준으로 오름차순이 되어있다. 1초단위로 체크를 해야하는데, 시작점을 어디로 잡아야 최대한의 카운팅을 하면서 시작할 수 있을까... 라는 생각을 해봐야한다.

기준으로 잡은 노드(현재노드)의 종료시간을 1초체크의 시작으로 삼아보자. 사실상 시작하자마자 카운팅을 1개하고 시작하기 때문에 괜찮은 것 같다.

그러면 이제 그 다음노드들을 검사하면서 카운팅해야하는데, 어떤 조건으로 검사해야 할 것인가.

그다음 노드들은 종료시간은 현재노드보다 무조건 더 크긴 크다. 정렬되어서 값이 함수에 들어오기 때문이다.

그렇기때문에 단 한가지 경우를 제외하고는 1초체크범위에 들어온다.

다음노드의 시작시간이 1초체크의범위보다 클 경우이다. 이 경우를 제외하고는 무조건 범위안에 들기 때문에 카운팅이 된다. 1초체크범위보다 작다면, 그 어떠한 경우에도 카운팅 할 수 있다.

 

다음노드의 시작시간이 현재노드의 시작시간보다 작더라도 상관없다. -> 다음노드의 종료시간은 현재노드보다 반드시 크기 때문에, 0.001이라도 크면 체크범위안에 들어오게된다.

 

다음노드의 종료시간의 값이 지나치게 크더라도, 시작시간이 1초체크의범위보다 작으면 1초체크의범위안에 들어오게된다. 어떻게든 시작지점만 걸치면 카운팅조건이 되기 때문에 그 이후로는 값이 얼마나 크든 아무 상관이 없다.

 

이런 유형의 문제는 왠지 몇 번 더 나올것만 같다. 이번 문제를 접한 덕분에, 비슷한 유형의 문제가 나오면 좀 더 빨리 해결할 것 같다.