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

https://programmers.co.kr/learn/courses/30/lessons/17676

코딩테스트 연습 - [1차] 추석 트래픽

#include <string>
#include <vector>
#include <sstream>
#include <utility>
#include <algorithm>
using namespace std;
vector<pair<int, int> > times;

int check(int t){
    int sum=0;
    int t1=t+999;
    for (int i=0; i<times.size(); i++){
        if (times[i].second<t || t1<times[i].first){
            continue;
        }
        else{
            sum++;
        }
    }
    return sum;
}

int solution(vector<string> lines) {
    int answer = 0;
    int temp;
    string day, S, T;
    for (int i=0; i<lines.size(); i++){     //시작시간, 종료시간 넣어줌
        stringstream ss(lines[i]);
        string end="";
        ss>>day;
        ss>>S;
        ss>>T;
        for (int j=0; j<S.size(); j++){
            if (S[j]!=':' && S[j]!='.'){
                end+=S[j];
            }
        }
        int hour=stoi(end.substr(0,2))*3600*1000;
        int min=stoi(end.substr(2,2))*60*1000;
        int sec=stoi(end.substr(4,2))*1000;
        int msec=stoi(end.substr(6,3));
        int end_t=(hour+min+sec+msec);
        int dur=(stod(T.substr(0,T.size()-1))*1000)-1;
        int start_t=end_t-dur;
        times.push_back(make_pair(start_t, end_t));
    }
    for (int i=0; i<times.size(); i++){
        temp=max(check(times[i].first), check(times[i].second));
        answer=max(answer,temp);
    }
    return answer;
}

 

"시간 변환" 에서 꽤나 애를 먹어서 해결을 잘 못했던 문제.

이 문제의 포인트는 밀리초로 시간을 다 통합할 것(단위를 통합해서 59분 59초..가 00분 00초가 되는 순간에 대한 복잡한 처리를 하지 않아도 되도록 한다), 그리고 각 로그의 시작과 끝 부분을 기준으로 1초를 체크해서 구간에 들어가는 애들 세주고 최대값을 찾는 것 이 2가지다. 

 

이 문제에서 헤맨 부분은 시간을 변환하는 이슈였다. 시작, 끝 시간을 계산해야 되는데 59분 59초가 00분 00초로 넘어가는 순간을 어떻게 처리해서 계산할 것인가? 에 대한 부분을 오래 고민했다. 결론은 단위통합.

문자 그대로 20:59:59 이렇게 받아들이지 말고, 밀리초 단위로 변환해서 모든 시간을 나타내도록 하면 쉽게 시간 더하기 빼기가 가능하다. 한마디로, 시간, 분, 초 모두 밀리세컨드 단위로 변환해서 쉽게 연산하는 방법인 것이다.

 

의외로 구간을 체크하는 부분은 쉽게 아이디어를 떠올렸다.

로그 별로 2번 비교해주면 된다. (각 로그의 시작, 각 로그의 시작+1s), (각 로그의 끝, 각 로그의 끝+1s) 을 기준으로 속하는 다른 로그들의 개수를 세어주면 된다. 시간 복잡도는 따라서 O(N^2) 가 된다. 최대값이 2000개이므로 가볍게 넘어간다.

근데 여기서 오름차순으로 주어줬으므로 check 함수에서 사실 자기 다음 애부터~끝 애까지만 검사해줘도 된다.

 

나와 다른 방식으로 비교한 분들도 있다.(출처: https://velog.io/@mrbartrns/%ED%8C%8C%EC%9D%B4%EC%8D%AC-1%EC%B0%A8%EC%B6%94%EC%84%9D-%ED%8A%B8%EB%9E%98%ED%94%BD-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%A0%88%EB%B2%A83)

  for i in range(len(lines)):
        cnt = 0
        cur_end_time = end_time[i]
        # i번째는 현재 자신의 시작시간이고, i 이하는 그 이전의 시작시간이므로 카운트 할 필요가 없다.
        for j in range(i, len(lines)):
            if cur_end_time > start_time[j] - 1000:
                cnt += 1
        answer = max(answer, cnt)

어차피 종료 시간대로 오름차순 정렬되어 있으므로, 

종료 시간+1000 > 내 다음 애의 시작 시간 이래도 구간에 속한 거니까 +1 해준다.