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

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

using namespace std;

int getTime(string time)
{
    return stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3, 2));
}

bool cmp(vector<string>a, vector<string>b)
{
    return a[1] < b[1];
}

vector<string> solution(vector<vector<string>> plans) {
    vector<string> answer;
    stack<pair<string, int>>pause;
    
    sort(plans.begin(), plans.end(), cmp);
    
    for(int i=0; i<plans.size()-1; i++)
    {
        string name = plans[i][0]; //과제 이름
        int start = getTime(plans[i][1]); //시작 시간
        int playtime = stoi(plans[i][2]); //진행 시간
        int next_start = getTime(plans[i+1][1]); //다음 시작 시간
        int remain = next_start-start; //다음 시간까지 간격
        
        if(remain>=playtime) 
        {
            answer.push_back(name); //과제 수행
            remain -= playtime;
            
            while(!pause.empty()) //멈춘 과제
            {
                auto [pname, ptime] = pause.top();    
                pause.pop();
                if(remain >= ptime)
                {
                    answer.push_back(pname);
                    remain-=ptime;
                }
                else
                {
                    pause.push({pname, ptime-remain});
                    break;
                }
            }
        }
        else
        {
            pause.push({name, playtime - remain});
        }
    }
    
    answer.push_back(plans.back()[0]); //마지막 과제
    
    while(!pause.empty()) //남은 과제
    {
        answer.push_back(pause.top().first);
        pause.pop();
    }
    
    return answer;
}

 

시작 시간 순으로 정렬해주어야 하기에 따로 비교 함수를 만들어서 적용시켜주고 시작하자.

시작 시간과 다음 시작 시간을 미리 선언해서 이를 통해 다음 시작시간 까지의 간격을 구하고 이를 통해 하나씩 구현해주었다.

 

먼저 해당 간격이 진행 시간이보다 크거나 같다면 현재 과제는 무사히 수행이 가능할 것이다.

이제 수행한 시간을 제거하여 남은 시간을 체크하자.

 

만약 멈춰논 과제가 있다면 멈춰놨던 과제의 진행 시간을 체크하고, 가능한 경우 마찬가지로 해당 과제를 무사히 수행하고 수행한 시간만큼 또 남은 시간을 계산해주자.

만약 불가능하다면 해당 과제에 대해 남은 시간만큼 진행하고 또 남은 시간에 대해 다시 저장해주자.

멈춰논 과제들은 누적해서 저장이 될 수 있고, 처음 저장한 값이 뒤로 밀리기 때문에 후입선출인 stack을 통해 밀린 과제를 처리해줄 필요가 있다.

 

이후 다시 원 과제 수행으로 돌아와서, 해당 과제에 대해서도 비슷하게 수행이 불가하면 가능한 시간만큼만 진행하고 다시 남은 시간을 저장한다.

이를 모든 값에 대해서 반복수행한다.

 

그러면 마지막 과제가 남아있을 것이다.

마지막 과제는 무조건 수행가능하기에 바로 수행해주고, 남은 멈춰논 과제들도 하나식 순차적으로 수행해주면 된다.