[프로그래머스] Level 2. 과제 진행하기

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

프로그래머스

 

해결 방법

1. 과제 시작시간이 빠른 순서대로 정렬한다.
2. 현재시간을 나타내는 minute 과 , 미완료 과제의 남은 작업시간을 저장하는 스택 task를 선언한다.
3. 내 작업을 시작하기에 앞서, 현재시간과 작업 시작 시간 사이의 gap 이 다른과제를 할 찬스이다.
4. 이 시간동안 스택에서 작업들을 꺼내와 작업을 수행한다. 만약 남은 작업이 없거나, 짬 나는 시간을 모두 다 사용해서 새로운 과제를 시작해야 할 시간이 오면, 그 작업을 스택에 넣고 다음으로 넘어간다.
5. 이렇게에서 스택에서 가장먼저 빠져나온 과제물 순서를 찾는다

 

#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <iostream>

using namespace std;


vector<string> solution(vector<vector<string>> plans) {
    vector<string> answer;
    stack<pair<int,int>> task;
    
    sort(plans.begin(), plans.end(), [](vector<string>& a, vector<string>& b){return a[1]<b[1];}); //과제 시작 시간순으로 정렬
    
    int minute = 0;
    for(int i =0; i<plans.size(); i++){
        
        //다음 작업시작 시간(시간*60+분)
        int crrTs = stoi(plans[i][1].substr(0,2)) * 60 + stoi(plans[i][1].substr(3,2));

        //plans[i] 과제를 시작하기 전, 남은시간동안 못다한 과제를 하자.
        while(!task.empty()){
            auto& p = task.top(); 
            int gap = crrTs - minute;
            
            if(p.second > gap){ //앞에과제 하다가 끊김.작업 할수있는데까지 함.
                p.second -= gap;
                break;
            }
            
            //앞에 과제 완료하였음. answer에 넣어주고 스택에서 제거.
            task.pop();
            answer.push_back(plans[p.first][0]);
            minute += p.second;
        }
        
        //이제 plans[i] 과제를 해야함. 스택에넣어줌
        minute = crrTs;
        task.push(make_pair(i,stoi(plans[i][2])));
    }
    
    //제한시간 안에 못한 과제들 마저 완료
    while(!task.empty()){
        auto& p = task.top();
        answer.push_back(plans[p.first][0]);
        task.pop();
    }
    
    return answer;
}