프로그래머스 - 추석 트래픽

출처 : https://www.acmicpc.net/problem/programmers.co.kr/learn/courses/30/lessons/17676 

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

 

고려사항

• 정보 파싱하는 메소드 구현, ' ' 와 ':' 를 인자로 넘겨주어 파싱.  ( 9 - 22 )
• 날짜는 무의미하고, 시간 정보는 모두 ms 로 변환해서 각각 시작 시간 벡터, 종료 시간 벡터에 담는다. ( 24 - 34 )
• 시작 시간, 종료 시간이 있는 지점이 트래픽 cnt 가 변하는 구간이다.
  각각의 배열을 돌면서, 해당 시간 기준으로 999 만큼 더한 기준 시간을 구한다.
  ( 시작 시간도 포함이니 1초는 1000이 아니라, 시작 시간 + 999 가 1초이다. )
  ( 같은 맥락으로, 시작 시간을 구할 때에는, 종료 시간 - 소요 시간 + 1 이다. ms 단위 기준! )
• 구한 시간의 범위에 포함되는 트래픽인지 판별 하기. (36 - 50 )
  1. 구한 범위의 시작 시간 <= 조사중인 인덱스의 시작 시간 <= 구한 범위의 종료 시간
  2. 구한 범위의 시작 시간 <= 조사중인 인덱스의 종료 시간 <= 구한 범위의 종료 시간
  3. 조사중인 인덱스의 시작 시간 <= 구한 범위 <= 조사중인 인덱스의 종료 시간 
  (3 번 조건을 간과해서 2, 3, 18 총 3개의 테스트 케이스만 계속해서 틀렸다...)
• 모든 트래픽 시간을 기준으로 판별하며 최대값을 찾느다. ( 63 - 79 )
  ( 트래픽의 시작 시간, 종료 시간을 기준으로 모두 판별! )

 

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

vector<int> startTime;
vector<int> endTime;

vector<string> parse(string str, char c){
    vector<string> ret;
    int cur = 0, prev = 0;

    cur = str.find(c);
    while(cur != -1){
        ret.push_back(str.substr(prev, cur-prev));
        prev = cur + 1;
        cur = str.find(c, prev);
    }
    ret.push_back(str.substr(prev, -1));

    return ret;
}

void makeTimeTable(vector<string> &v){
    vector<string> num = parse(v[1], ':');
    int sum = 0;

    sum += stoi(num[0]) * 1000 * 60 * 60;
    sum += stoi(num[1]) * 1000 * 60;
    sum += stof(num[2]) * 1000;

    startTime.push_back(sum - (stof(v[2])*1000) + 1);
    endTime.push_back(sum);
}

bool checkPossible(int s, int e, int index){
    int targetStart = startTime[index];
    int targetEnd = endTime[index];
    bool ret = false;
    
    if(targetStart >= s && targetStart <= e){
        ret = true;
    }else if(targetEnd >= s && targetEnd <= e){
        ret = true;
    }else if(targetStart <= s && targetEnd >= e){
        ret = true;
    }
    
    return ret;
}

int solution(vector<string> lines) {
    int answer = -1;
    int len = lines.size();
    int cnt;
    
    for(string str : lines){
        vector<string> v = parse(str, ' ');
        v[2].pop_back();
        makeTimeTable(v);
    }

    for(int i=0;i<len;++i){
        cnt = 0;
        for(int j=0;j<len;++j){
            if(checkPossible(startTime[i], startTime[i]+999, j)){
                ++cnt;
            }
        }
        answer = max(answer, cnt);

        cnt = 0;
        for(int j=0;j<len;++j){
            if(checkPossible(endTime[i], endTime[i]+999, j)){
                ++cnt;
            }
        }
        answer = max(answer, cnt);
    }

    return answer;
}