과제 진행하기(50분)

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

구현 아이디어 3분 구현 47분

풀이

분명 이렇게 구현하면 되겠다! 하고 풀었는데 구현에 47분이나 걸렸다. 조건은 어렵지 않은데 잡는게 어려웠다... 다음 번엔 30분만에 풀자!

#include <string>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

struct Data
{
    string name;
    int start;
    int playtime;
    Data(string n, int s, int p)
    {
        name = n;
        start = s;
        playtime = p;
    }
    bool operator<(const Data& b) const
    {
        return start > b.start;
    }
};

int conv(string s)
{
    int h = (s[0] - '0') * 10 + (s[1] - '0');
    int m = (s[3] - '0') * 10 + (s[4] - '0');
    
    return h * 60 + m;
}

vector<string> solution(vector<vector<string>> plans) {
    vector<string> answer;
    
    int N = plans.size();
    
    priority_queue<Data> pQ;
    stack<Data> stk;
    
    for(int i = 0; i < N; ++i)
    {
        string name = plans[i][0];
        int start = conv(plans[i][1]);
        int playtime = stoi(plans[i][2]);
        pQ.push(Data(name, start, playtime));
    }
    
    bool first = true;
    int curtime = pQ.top().start;
    Data curplan("", 0, 0);
    
    while(!pQ.empty())
    {
        Data a = pQ.top();
        
        // 현재 시각이 a의 시작 시간과 같다면.
        if(curtime == a.start)
        {
            // 원래 하던 것이 끝났다.
            if(curplan.playtime == 0 && !first)
                answer.push_back(curplan.name);
            // 원래 하던 것이 아직 남았다.
            else if(curplan.playtime > 0 && !first)
                stk.push(curplan);
            
            pQ.pop();
            curplan = a;
        }
        
        if(curplan.playtime == 0)
        {
            answer.push_back(curplan.name);
            if(!stk.empty())    
            {
                curplan = stk.top();
                stk.pop();
            }
        }
        
        if(pQ.empty())
        {
            answer.push_back(a.name);
            break;
        }
        
        --curplan.playtime;
        ++curtime;
        first = false;
    }
    
    while(!stk.empty())
    {
        answer.push_back(stk.top().name);
        stk.pop();
    }
    
    return answer;
}

---

풀이

시간을 1씩 늘리지 않고 다음 과제 시간과 현재 과제 시간의 차이를 가지고 조건에 따라 시간이 변하게 했다. 다음에 참고할 일이 있을까하여 주석을 꼼꼼하게 달아놓았다.

#include <string>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

struct Data
{
    string name;
    int start;
    int playtime;
    Data(string n, int s, int p)
    {
        name = n;
        start = s;
        playtime = p;
    }
    bool operator<(const Data& b) const
    {
        return start > b.start;
    }
};

int conv(string s)
{
    int h = (s[0] - '0') * 10 + (s[1] - '0');
    int m = (s[3] - '0') * 10 + (s[4] - '0');
    
    return h * 60 + m;
}

vector<string> solution(vector<vector<string>> plans) {
    vector<string> answer;
    
    int N = plans.size();
    
    priority_queue<Data> pQ;
    stack<Data> stk;
    
    for(int i = 0; i < N; ++i)
    {
        string name = plans[i][0];
        int start = conv(plans[i][1]);
        int playtime = stoi(plans[i][2]);
        pQ.push(Data(name, start, playtime));
    }
    
    int curtime = pQ.top().start;
    
    while(!pQ.empty())
    {
        if(curtime == pQ.top().start)
        {
            // 현재 진행할 과제.
            Data curplan = pQ.top();
            pQ.pop();
            
            // 다음 과제.
            Data nextplan = pQ.top();
            
            // 다음 과제와 지금 과제 간의 시간 차이.
            int sub = nextplan.start - curplan.start;
            
            // 이 시간 차이가 지금 과제의 수행 시간보다 작다면.
            if(sub < curplan.playtime)
            {
                // 0 초과의 시간이 나올 것임.
                curplan.playtime -= sub;
                
                // 다 할 수 없으니 스택에 넣음.
                stk.push(Data(curplan));
                
                // 현재 시간을 시간 차이만큼 늘려줌. 다음 루프 때 다음 과제를 꺼낼 것임.
                curtime += sub;
            }
            
            // 시간 차이가 지금 과제 수행 시간과 같다면 과제를 수행할 수 있음.
            else if(sub == curplan.playtime)
            {
                answer.push_back(curplan.name);
                curtime += curplan.playtime;
            }
            
            // 시간 차이가 지금 과제 수행 시간보다 크다면 이 과제를 수행하고 스택에 있는 과제도 진행할 수 있음.
            // 다만 스택에 있는 과제는 다음 과제 시작 시간까지만 진행할 수 있음.
            else if(sub > curplan.playtime)
            {
                answer.push_back(curplan.name);
                curtime += curplan.playtime;
                
                while(!stk.empty() && curtime < nextplan.start)
                {
                    // 멈춰둔 과제.
                    Data& pauseplan = stk.top();
                    
                    // curtime과 nextplan의 start 타임 차 다시 계산해야 함.
                    // (위에서 바뀌었기 때문)
                    int sub = nextplan.start - curtime;
                    
                    // sub 만큼 멈춰둔 과제 진행 가능.
                    // sub가 크다면 멈춰둔 과제 완료 가능.
                    if(sub >= pauseplan.playtime)
                    {
                        answer.push_back(pauseplan.name);
                        stk.pop();
                        curtime += pauseplan.playtime;
                    }
                    // sub가 멈춰둔 과제 수행 시간보다 작다면 sub 만큼 playtime에서 빼고 스택에서 빼지는 않음.
                    else
                    {
                        pauseplan.playtime -= sub;
                        curtime += sub;
                    }
                }
                
                // 시간이 남는 경우에 스택에 아무 원소도 없을 경우 다음 과제 진행 시간으로 현재 시간 갱신.
                if(stk.empty()) curtime = nextplan.start;
            }
        }
    }
    
    while(!stk.empty())
    {
        answer.push_back(stk.top().name);
        stk.pop();
    }
    
    return answer;
}