[알고리즘/C++] 프로그래머스 - 과제 진행하기 (Lv.2)

✏️ 풀이 방법
1. plans를 시작시간이 빠른 순서대로 정렬
(문자열 그대로 정렬 가능)
2. 정보를 가져오기 편하도록 [과제 이름, (시작시간, 소요시간)] 형태로 map 저장
3. 정렬된 첫 과제를 스택에 저장
4. 정렬 리스트를 돌면서
    4-1. 이전 과제의 종료시간 == 현재 과제의 시작시간
    4-2. 이전 과제 종료시간이 현재 과제 시작시간보다 늦을 때
    4-2. 이전 과제 종료시간이 현재 과제 시작시간보다 빠를 때
인 경우의 수를 고려함
5. 진행중인 과제가 바뀔 경우 lastFinishTime 변수에 현재 과제의 예상 종료시간을 저장,
이전 과제의 시작시간을 현재 과제의 예상 종료시간으로 변경

c++

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

using namespace std;

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

map<string, tuple<int, int>> ConvertPlans(vector<vector<string>> plans)
{
    map<string, tuple<int, int>> converted;

    for (int i = 0; i < plans.size(); ++i)
    {
        int startMin = stoi(plans[i][1].substr(0, 2)) * 60 + stoi(plans[i][1].substr(3, 2));
        int playMin = stoi(plans[i][2]);

        converted[plans[i][0]] = make_tuple(startMin, playMin);
    }

    return converted;
}

vector<string> solution(vector<vector<string>> plans)
{
    vector<string> answer;

    sort(plans.begin(), plans.end(), cmp);

    map<string, tuple<int, int>> plansMap = ConvertPlans(plans);

    stack<string> stackPlans;
    stackPlans.push(plans[0][0]);

    int lastFinishTime = get<0>(plansMap[stackPlans.top()]);

    for (int i = 1; i < plans.size(); ++i)
    {
        int prevLeftTime = get<1>(plansMap[stackPlans.top()]);
        int prevStartTime = get<0>(plansMap[stackPlans.top()]);
        int prevEndTime = prevStartTime + prevLeftTime;

        int currStartTime = get<0>(plansMap[plans[i][0]]);
        int currEndTime = currStartTime + get<1>(plansMap[plans[i][0]]);

        if (prevEndTime == currStartTime)
        {
            lastFinishTime = currEndTime;

            answer.push_back(stackPlans.top());
            stackPlans.pop();

            stackPlans.push(plans[i][0]);
        }
        else if (prevEndTime > currStartTime)
        {
            lastFinishTime = currEndTime;

            plansMap[stackPlans.top()] = make_tuple(lastFinishTime, prevLeftTime - (currStartTime - prevStartTime));

            stackPlans.push(plans[i][0]);
        }
        else 
        {
            while (stackPlans.empty() == false && prevEndTime < currStartTime)
            {
                lastFinishTime = prevEndTime;

                answer.push_back(stackPlans.top());
                stackPlans.pop();

                if (stackPlans.empty() == false)
                {
                    prevEndTime = lastFinishTime + get<1>(plansMap[stackPlans.top()]);
                }
            }

            if (stackPlans.empty() == false)
            {
                plansMap[stackPlans.top()] = make_tuple(lastFinishTime, get<1>(plansMap[stackPlans.top()]));
                 i--;
                continue;
            }
            else
            {
                stackPlans.push(plans[i][0]);
                lastFinishTime = currEndTime;
            }
        }
    }

    while (stackPlans.empty() == false)
    {
        answer.push_back(stackPlans.top());
        stackPlans.pop();
    }

    return answer;
}

✏️ 다른 해결 방법
루프의 기준을 정렬된 리스트 순회가 아닌 stack.empty() 인 경우로 두고 푸는 코드가 있었다.
반복문이 돌 때 마다 해당 과제의 소요시간을 감소시켜 시간을 관리한다.