과제 진행하기

시물레이션 문제라고 생각한다. 항상 지나가다가 문제를 보고 푸는걸 미뤘는데 문제를 보면서 계속 생각해보니 풀이 법이 나와서 기분이 참 좋았다.

좀 특이한 점은... PQ를 사용하면서 Object를 사용할때는 Comparator을 따로 만들어서 얹여 줘야 한다. 난 이떄 greater<> 구현을 위해서 JobCompare 을 만들어줬다.

확실히 그냥 일반적인 PQ로 구현하려고 하니 힘들었는데 이렇게 하니깐 훨씬 편했다. 또 특이점은... 새로운 과제가 우선적으로 고려되야 하기때문에 그에 맞게 구현을 조금 바꿔줬다.

#include <string>
#include <vector>
#include <bits/stdc++.h> 
using namespace std;

struct Job{
    int start_time, duration;
    string subject; 
};

struct JobCompare
{
  bool operator()(const Job& lhs, const Job& rhs) const
  {
    return lhs.start_time > rhs.start_time;
  }
};

vector<string> solution(vector<vector<string>> plans) {
    vector<string> answer;
    sort(plans.begin(), plans.end(), [](vector<string>& a, vector<string>& b){
        return a[1] < b[1];
    });    
    
    priority_queue<Job, vector<Job>, JobCompare> pq; 
    stack<Job> lastJob; 
    
    for(vector<string>& v : plans){
        int sT = stoi(v[1].substr(0,2)) * 60 + stoi(v[1].substr(3)); 
        int duration = stoi(v[2]); 
        pq.push({sT, duration, v[0]});
    }
    
     while(!pq.empty()){
         int size = pq.size();
         
         for(int i = 0; i < size; i++){
             Job job = pq.top();
             pq.pop(); 
             
             int start_time = job.start_time, duration = job.duration;
             string subject = job.subject; 
             bool flag = false; 
             if(!pq.empty()){
                 Job next = pq.top(); 
                 int next_startTime = next.start_time, next_duration = next.duration;
                 string next_subject = next.subject; 
                 if(start_time + duration > next_startTime){
                     flag = true; 
                     int diff = next_startTime - start_time; 
                     lastJob.push({start_time, duration - diff, subject});
                 }
             }
             
             if(!flag){ //아무 이슈 없이 끝낸 상황
                 answer.push_back(subject); 
                 if(!lastJob.empty()){
                     Job left = lastJob.top(); 
                     
                     if(!pq.empty() && pq.top().start_time == start_time + duration){
                         continue;
                     } else{
                         lastJob.pop(); 
                         pq.push({start_time + duration, left.duration, left.subject}); 
                     }
                 }
             }
             
         }
     }
    
    return answer;
}