프로그래머스 과제 진행하기 - C++ 풀이

---

 

1. 시작시간을 기준으로 오름차순 정렬하여 순차적으로 시작한다.
2. 현재 과제를 끝내기 전에 다음 과제를 시작해야 하는 경우, 현재 과제를 중단한다. 중단된 과제들은 스택으로 관리한다.
3. 다음과제를 시작하기 전까지 텀이 존재하는 경우, 텀 동안 중단했던 과제들을 해결한다.

 

1. 시작시간을 기준으로 오름차순 정렬하여 순차적으로 시작한다.

 시작시간에 맞춰 순차적으로 시작해야하므로, 시작시간을 기준으로 오름차순 정렬해둔다.

 

2. 현재 과제를 끝내기 전에 다음 과제를 시작해야 하는 경우, 현재 과제를 중단한다. 중단된 과제들은 스택으로 관리한다.

 만약 현재 과제를 끝내기 전에 다음 과제를 시작해야 하는 경우, 현재 과제를 중단해야 한다. 이때 중단된 과제들은 스택에 넣어둔다. 멈춰둔 과제가 여러 개일 경우, 가장 최근에 멈춘 과제부터 시작해야 한다는 조건이 있기 때문에 LIFO 구조가 적합하기 때문이다.

 

3. 다음과제를 시작하기 전까지 텀이 존재하는 경우, 텀 동안 중단했던 과제들을 해결한다.

 만약 다음 과제를 시작하기 전까지 텀이 존재하는 경우, 현재 과제를 끝낸 뒤 텀 동안 중단했던 과제들을 스택에서 하나씩 뽑아 해결해준다.

---

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

using namespace std;

struct Assignment {
    string title;
    int startTime;
    int playTime;
};

int toInt(char c) {
    return c - '0';
}

int timeToInt(string t) {
    return (toInt(t[0]) * 10 + toInt(t[1])) * 60 + (toInt(t[3]) * 10 + toInt(t[4]));
}

bool cmp(const Assignment& lhs, const Assignment& rhs) {
    return lhs.startTime < rhs.startTime;
}

vector<string> solution(vector<vector<string>> plans) {
    vector<string> answer;
    int n = plans.size();
    vector<Assignment> assignments;
    
    for (auto plan: plans) {
        string title = plan[0];
        int startTime = timeToInt(plan[1]);
        int playTime = stoi(plan[2]);
        
        assignments.push_back({title, startTime, playTime});
    }
    
    // 시작 시간 기준 오름차순 정렬
    sort(assignments.begin(), assignments.end(), cmp);
    
    stack<Assignment> paused;
    Assignment curr = assignments[0];
    
    for (int i=1; i<n; i++) {
        Assignment next = assignments[i];
        int term = next.startTime - (curr.startTime + curr.playTime);
        
        // 다음 과제까지 텀이 있는 경우
        if (term >= 0) {
            // 현재 과제 끝내기
            answer.push_back(curr.title);
            
            // 남은 시간(텀)동안 중단했던 과제들 재개하기
            while (term > 0 && !paused.empty()) {
                int resumeTime = min(paused.top().playTime, term);
                paused.top().playTime -= resumeTime;
                term -= resumeTime;
                
                // 중단했던 과제 완료
                if (paused.top().playTime <= 0) {
                    answer.push_back(paused.top().title);
                    paused.pop();   
                }
            }
        }
        // 텀이 없는 경우
        else {
            // 현재 과제 중단
            curr.playTime -= (next.startTime - curr.startTime);
            paused.push(curr);
        }
        
        // 다음 과제 시작
        curr = next;
    }
    
    // 현재 과제 끝내기
    answer.push_back(curr.title);
    
    // 중단된 과제들 다 해결하기
    while (!paused.empty()) {
        answer.push_back(paused.top().title);
        paused.pop();
    }
    
    return answer;
}