프로그래머스 - 과제 진행하기

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

프로그래머스

---

문제 설명

다음과 같은 규칙을 가지고 과제를 진행해야합니다.

• 과제는 시작하기로 한 시각이 되면 시작합니다.
• 새로운 과제를 시작할 시각이 되었을 때, 기존에 진행 중이던 과제가 있다면 진행중이던 과제를 멈추고 새로운 과제를 시작합니다.
• 진행중이던 과제를 끝냈을 때, 잠시 멈춘 과제가 있다면, 멈춰둔 과제를 이어서 진행합니다.
  이 때 과제를 끝낸 시각에 새로 시작해야 하는 과제와 잠시 멈춰둔 과제가 모두 있다면 새로 시작해야 하는 과제부터 진행합니다.
• 멈춰둔 과제가 여러개라면 가장 최근 멈춘 과제부터 시작합니다. 
• 과제의 계획을 담은 이차원 문자열 배열 plans는 정렬되어 있지 않을 수 있습니다.

과제의 계획을 담은 이차원 문자열 배열 plans가 주어질 때, 과제를 끝낸 순서대로 이름을 리턴하시오.

plans = [ 과제명, 시작시각, 남은시간]
시작 시간은 hh:mm이며 남은 시간은 1~100 사이 분 형태입니다.

---

아이디어

과제를 시작하기로 한 시각이 되면 시작합니다.
→ 과제 사이사이를 남은 시간을 사용해 뛰어넘으면서 하면 효율적이겠지만, 직관적이고 쉽게 for(시작시각 ~ 종료시각)으로 작성해도 될 것 같습니다. 

새로운 과제가 있으면 기존 과제를 잠시 멈춥니다.
→ 모든 과제가 끝났다면 남은 과제를 한 번에 해도 됩니다.

멈춰둔 과제가 여러개라면 가장 최근 멈춘 과제부터 시작합니다 
→ 스택 구조로 멈춘 과제를 하나씩 넣으면 될 것 같습니다. 또한 스택 가장 뒤에 과제만 신경써서 관리하면 문제 해결이 가능합니다.

과제 계획 plans는 정렬되어 있지 않을 수 있습니다.
→ 정렬을 미리 해두는게 순차적으로 확인하기 좋을 것 같습니다.

---

코드

#include <bits/stdc++.h>

using namespace std;

#define leftTime first
#define planNum second

vector<string> Split(string str)
{
    istringstream iss(str);
    string buffer;
    vector<string> ret;
    
    while(getline(iss, buffer, ':'))
    {
        ret.push_back(buffer);
    }
    return ret;
}

int GetTime(string str)
{
    auto time = Split(str);
    return stoi(time[0]) * 60 + stoi(time[1]);
}

vector<string> solution(vector<vector<string>> plans) {
    vector<string> answer;
    
    //1. sort
    sort(plans.begin(), plans.end(), 
         [](vector<string> a, vector<string> b) 
         { 
             auto aTime = GetTime(a[1]); 
             auto bTime = GetTime(b[1]);
             return aTime < bTime;
         });
    
    //2. start ~ end
    int startTime = GetTime(plans[0][1]);
    int endTime = GetTime(plans.back()[1]);
    vector<pair<int, int>> stack; // leftTime, plansNum
    int currentIndex = 0;
    int NextTime = startTime;
    for(int i = startTime; i < endTime; ++i)
    {
        if(!stack.empty())
        {
            stack.back().leftTime -= 1;
            if(stack.back().leftTime == 0)
            {
                answer.push_back(plans[stack.back().planNum][0]);
                stack.pop_back();
            }
        }
        if(NextTime == i)
        {
            stack.push_back({stoi(plans[currentIndex][2]), currentIndex++});
            NextTime = GetTime(plans[currentIndex][1]);
        }
    }
    
    //3. last subject check
    if(!stack.empty())
    {
        stack.back().leftTime -= 1;
        if(stack.back().leftTime == 0)
        {
            answer.push_back(plans[stack.back().planNum][0]);
            stack.pop_back();
        }
    }
    stack.push_back({stoi(plans[currentIndex][2]), currentIndex});
    
    //4. left subjects finsih
    while(!stack.empty())
    {
        answer.push_back(plans[stack.back().planNum][0]);
        stack.pop_back();
    }
    return answer;
}

메모리 4.14MB, 시간 12.58ms
sort GetTime 제외시 메모리 4.24MB, 시간 3.79ms

---

• sort 시간비교는 GetTime 안넣고 그냥 해도 되며 더 빠릅니다.
• 2. start ~ end에서 기존에는 과제명을 직접 보관했는데 문자열 복사가 커서 그런지 과제에 index 저장으로 수정했습니다.
• 다음 과제에 시작 시간을 체크할 때, 마지막 과제는 제외해서 3.last subject check로 따로 했습니다. currentIndex++ 말고 다른 걸로 바꾸는 것보다는 간편하고 for 내부에서 if를 계속 돌리는 것 보다는 효율적인것 같습니다.