[2018 KAKAO BLIND RECRUITMENT 1차] 추석트래픽

문제풀이

 

핵심이되는 부분은

각 타임별 스타트 지점 끝지점을 기준으로 겹치는 부분을 확인하는 것이다.

 

중간에 포함이 될수도있고, 넘칠수도있고, 뒤만 걸칠수도있고, 앞만 들어갈수도있다. 모든 경우를 다 따져가는 코딩방식이다. 

 

시작지점후 1초, 끝지점후 1초를 모두 비교한다. 

 

매우 복잡하다. 시간을 변경하는 건 무난 했으나 나머지 구현이 좀 복잡한 문제였던 것 같다. 

 

 

소스코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
 
typedef struct Time{
    int start;
    int end;
    Time(){}
    Time(string hour, string min, string sec, string m_sec, string p_time){
        int hh = stoi(hour) * 60 * 60 * 1000;
        int mm = stoi(min) * 60 * 1000;
        int ss = stoi(sec) * 1000;
        int ms = stoi(m_sec);
        int pt = (int)(stod(p_time)*1000);
        end = hh + mm + ss + ms;
        start = end - pt +1;
    }
}Time;
 
vector<Time> time_datas;
 
bool cmp(Time t1, Time t2) {
    return t1.start < t2.start;
}
 
int solution(vector<string> lines) {
    
    int cnt=0,max_cnt=0;
    
    string hour, min, sec, m_sec, p_time;
    
    for(int i=0;i<lines.size();i++){
        hour = lines[i].substr(11,2);
        min = lines[i].substr(14,2);
        sec = lines[i].substr(17,2);
        m_sec = lines[i].substr(20,3);
        p_time = lines[i].substr(24);
        
        p_time.pop_back();
        time_datas.push_back(Time(hour,min,sec,m_sec,p_time));
    }
    
    sort(time_datas.begin(),time_datas.end(),cmp);
    
    for(int i=0; i<time_datas.size();i++){
        cnt=0;
        for(int j=0;j<time_datas.size();j++){
            if(time_datas[i].start <= time_datas[j].start &&time_datas[i].start+999>=time_datas[j].start)
                cnt++;
            else if(time_datas[i].start>=time_datas[j].start && time_datas[i].start<=time_datas[j].end)
                cnt++;
            else if(time_datas[i].start + 999 < time_datas[j].start)
                break;
            if(max_cnt < cnt)
                max_cnt = cnt;
        }
        
    }
    
    
    for( int i=0;i<time_datas.size();i++){
        cnt=0;
        for(int j=0;j<time_datas.size();j++){
            if(time_datas[i].end<=time_datas[j].start && time_datas[i].end + 999 >= time_datas[j].start)
                cnt++;
            else if(time_datas[i].end>=time_datas[j].start && time_datas[i].end <= time_datas[j].end)
                cnt++;
            else if(time_datas[i].end + 999 < time_datas[j].start)
                break;
            if( max_cnt < cnt)
                max_cnt = cnt;
        }
    }
    
    return max_cnt;
}
 

 

 

문제 링크 : www.programmers.co.kr/learn/courses/30/lessons/17676

프로그래머스