[프로그래머스LV2] 과제 진행하기 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/176962

프로그래머스

 

Greedy 라고 해야할까? 일반적인 구현문제이다. 주어진 조건을 잘 지키면 되지만 문자열로 주어진 시간을 분단위로 어떻게 잘 바꿔서 컨트롤할 수 있느냐가 관건인 문제였다. 

 

우선순위 큐를 사용해 진행해야하는 밀린 과제들을 컨트롤 해 주었다.

 

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

pair<int, int> timesplit(string times){
    string hour = "";
    hour.push_back(times[0]);
    hour.push_back(times[1]);
    
    string min = "";
    min.push_back(times[3]);
    min.push_back(times[4]);
    
    return {stoi(hour), stoi(min)};
}

bool comp(vector<string> &a , vector<string>& b){
    pair<int, int> as = timesplit(a[1]);
    pair<int, int> bs = timesplit(b[1]);
    
    return as.first * 60 + as.second < bs.first * 60 + bs.second;
}

vector<string> solution(vector<vector<string>> plans) {
    vector<string> answer;
    
    sort(plans.begin(), plans.end(), comp);
    
    priority_queue<pair<int, pair<string, int>>> readyQ;
    
    for(int i = 0; i < plans.size() - 1; i++){
        pair<int, int> times = timesplit(plans[i][1]);
        int nowTime = times.first * 60 + times.second;
        int workEndTime = times.first * 60 + times.second + stoi(plans[i][2]);
    
        pair<int, int> nextTime = timesplit(plans[i + 1][1]);
        
        int nextStartTime = nextTime.first * 60 + nextTime.second;
        
        
        if(workEndTime <= nextStartTime){ // 이번에 과제를 끝낼 수있음
            answer.push_back(plans[i][0]);
            
            int garbageTime = nextStartTime - workEndTime;
            
            while(!readyQ.empty() && garbageTime > 0){
                int idx = readyQ.top().first;
                string name = readyQ.top().second.first;
                int readyTime = readyQ.top().second.second;
                readyQ.pop();
                if(readyTime <= garbageTime){
                    garbageTime -= readyTime;
                    answer.push_back(name);
                }else{
                    readyTime -= garbageTime;
                    readyQ.push({idx, {name, readyTime}});
                    
                    break;
                }
            }
        }else { // 이번엔 끝낼 수 없음
            int needtime = stoi(plans[i][2]);
            int needTime = needtime - (nextStartTime - nowTime);
            
            readyQ.push({i, {plans[i][0], needTime}});
        }
    }
    answer.push_back(plans[plans.size() - 1][0]);
//     readyQ.push({plans.size(), {plans[plans.size() - 1][0], stoi(plans[plans.size() - 1][2])}});
    
    while(!readyQ.empty()){
        answer.push_back(readyQ.top().second.first);
        readyQ.pop();
    }
    
    return answer;
}