[프로그래머스] 추석 트래픽

아이디어

• 시뮬레이션을 구현할 줄 안다.

접근방식

1. 각 시, 분, 초를 전부 초로 변환하여 끝나는 시간, 처리시간을 저장한다
2. 끝나는 시간 - 처리시간 + 0.001 을 통해 시작 시간을 구해 저장한다
3. 시작시간 -> 끝나는 시간 순으로 작은 순서로 sort를 진행한다
4. priority_queue를 사용해서 '끝나는 시간' 이 작은 순서대로 음수를 곱해서 저장한다(priority queue는 큰 숫자를 우선순위를 높게 치기에, 음수를 넣어 저장해준다)
5. 각 시작 시간에서 q.top을 계속 비교해서 q.pop()을 해준다. (뒤 시작시간 - 앞 끝시간 < 1 이면 무조건 이 시간 안에 실행하고 있다는 뜻이기 때문)

#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <iostream>
#include <queue>
#include <math.h>

using namespace std;

double end_t[2001];
double start_t[2001];
double work_t[2001]; // 실행 시간

void make_end(string s, int pos){ // 시작 시간,분,초,걸리는 시간
    double end_c = stod(s.substr(11,2)) * (double)3600.0;
    double end_m = stod(s.substr(14,2)) * (double) 60.0;
    double end_s = stod(s.substr(17,6));
    string temp = "";
    for(int i=24;i<s.size()-1;i++){
        temp.push_back(s[i]);
    }
    work_t[pos] = stod(temp);
    end_t[pos] = end_c+end_m+end_s;
}

void make_start(int pos){ // 끝나는 시간,분,초
    start_t[pos] = end_t[pos] - work_t[pos] + (double)0.001;
}

bool cmp (int a, int b){
   if(start_t[a] != start_t[b]) return start_t[a] < start_t[b];
    else if(end_t[a] != end_t[b]) return end_t[a] < end_t[b];
    else return a<b;
}



int solution(vector<string> lines) {
    int answer = 1;
    vector<int> v;
    for(int i=0;i<lines.size();i++){
        v.push_back(i);
        make_end(lines[i],i);
        make_start(i);
    }
    sort(v.begin(),v.end(),cmp);

    priority_queue<double> q;
    q.push(-end_t[v[0]]);


    for(int i=1;i<v.size();i++){ //start - end > 이면 계속 pop, 마지막에 push
        int next = v[i];
        while(!q.empty()){
            if(start_t[next] + q.top() >= (double)1) q.pop();
            else break;
        }
        q.push(-end_t[next]);
        answer = max(answer,(int)q.size());
    }

    return answer;
}

평가

큰 스킬은 필요가 없으나, 생각을 많이 해야하는 문제.
여기서 가장 중요한 아이디어는
1. 시,분,초를 초로 통일한다
2. 끝나는 시간, 시작시간을 비교해준다
인 것 같습니다.
저는 시,분,초를 나누어서 저장하다가, 굳이 그럴 필요가 없을 것 같아, 초로 통일해서 비교를 하였습니다. 그리고, 끝나는 시간이 다 다르기에, priority queue를 사용해서, 가장 빨리 끝나는 시간을 선택해 계속 pop해주는 식으로 진행하였습니다.
다만 문제의 아쉬운 점은, 처리시간,시작시간,끝나는 시간의 설명이 모호해서, 이를 이해하는데 시간이 좀 걸렸습니다.