[Algorithm] Programmers :: 과제 진행하기

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

프로그래머스

struct Node
{
    string name;
    int startTime;
    int remainingTime;
};
 
int convertTime(string s)
{
    int time = 0;
    if (s.size() == 5)
    {
        time = 600 * (s[0] - '0') + 60 * (s[1] - '0') + 10 * (s[3] - '0') + (s[4] - '0');
    }
    else
    {
        time = stoi(s);
    }
 
    return time;
}
 
bool cmp(const vector<string>& a, const vector<string>& b)
{
    int aTime = convertTime(a[1]);
    int bTime = convertTime(b[1]);
 
    return aTime <= bTime;
}
 
 
vector<string> solution(vector<vector<string>> plans)
{
    vector<string> answer;
 
    sort(plans.begin(), plans.end(), cmp);
    vector<Node> v;
 
    for (int i = 0; i < plans.size(); ++i)
    {
        v.push_back({ plans[i][0], convertTime(plans[i][1]), convertTime(plans[i][2]) });
    }
 
    stack<Node> s;
    v.push_back({ "dummy",3000000,1 });
    int curIndex = 0;
 
    while (curIndex < plans.size())
    {
        if (v[curIndex].startTime + v[curIndex].remainingTime <= v[curIndex + 1].startTime)
        {
            answer.push_back(v[curIndex].name);
 
            int remainingTimeForStack = v[curIndex + 1].startTime - v[curIndex].startTime - v[curIndex].remainingTime;
 
            while (!s.empty() && remainingTimeForStack > 0)
            {
                Node curNode = s.top();
 
                if (remainingTimeForStack >= curNode.remainingTime)
                {
                    s.pop();
                    answer.push_back(curNode.name);
                    remainingTimeForStack -= curNode.remainingTime;
                }
                else
                {
                    s.pop();
                    curNode.remainingTime -= remainingTimeForStack;
                    remainingTimeForStack = 0;
                    s.push(curNode);
                }
            }
            
        }
        else
        {
            s.push({ v[curIndex].name, v[curIndex].startTime, v[curIndex].startTime + v[curIndex].remainingTime - v[curIndex + 1].startTime });
        }
 
        ++curIndex;
    }
 
    return answer;
}
 

굳이 분류하자면 개인적으로 스택을 사용한 구현문제라 생각된다.

다루기 편하게 노드화해서 벡터로 따로 저장했으며, 반복문에서 인덱스검사를 위해 더미노드를 하나 더 넣어놓은 상태에서 로직을 수행했다.

 

일단 시작시간을 기준으로 먼저 오름차순 정렬을 했는데, 굳이 int형으로 변환할필요없이 그냥 string으로도 가능하긴 했다.

통과한다음 다른사람 코드보고 알아채기도 했고, 내가생각한 코드에선 int값으로 갖고 있어야해서 그대로 뒀다.

 

처음부터 순회를 할건데, 현재 과제의 시작시간 + 과제를 마치는데 걸리는 시간이 다음과제의 시작시간보다 '높다면', 즉

현재 과제를 수강하기 전에 다음과제의 시작시간이 되버린다면 수강한만큼의 시간을 차감 후, 스택에 넣어준다.

스택을 사용하는 이유는 문제의 조건이 잉여시간동안 '가장 최근에' 미뤄뒀던 과제를 먼저 완료해야 한다고 하기 때문이다.

 

반대로 현재과제의 시작시간 + 과제를 마치는데 걸리는 시간이 다음과목의 시작시간보다 '낮다면', 현재과제는 전부 끝낼 수 있다는 의미이기 때문에 answer에 푸쉬해준다.

그리고 다음과제 시작시간까지 잉여시간이 발생하기 때문에 해당시간동안 stack에 담겨있는 미뤄뒀던 과제들을 꺼내서 처리해주면 된다.