[프로그래머스] 과제 진행하기 C++ 풀이 및 해설

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

프로그래머스

 

풀이 방법

• 시작시간을 기준으로 plans를 오름차순으로 정렬한다.
• 문제에서 요구한 구현 방법으로 그대로 구현한다.
  • 그러나 시간을 11:11 문자열 형태로 제공하기에 이것을 다루기 편하기위해 분단위로 변경해서 계산한다.
  • 시작시각을 분단위로 변환했고 다른 과제의 시작시각 분단위보다 작다면 빨리 시작한다는 뜻이다.
  • 위의 방식으로 분단위로 변환해서 계산하면 과제 시작 시간과 종료시간, 남은시간 등을 관리하기 편하다.

상세한 풀이방식과 구현은 주석으로 상세히 달아놓았다. 참고!~

 

전체 코드

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

using namespace std;

bool comp(vector<string> a, vector<string> b) {
    
    a[1].erase(a[1].begin()+2);
    b[1].erase(b[1].begin()+2);
    
    if(stoi(a[1]) < stoi(b[1])) {
        return true;
    } else {
        return false;
    }
    
}


vector<string> solution(vector<vector<string>> plans) {
    vector<string> answer;
    stack<pair<int, string>> s; // (남은 과제 시간, 과제명)
    
    sort(plans.begin(), plans.end(), comp); // 시간순 정렬 ":" 문자를 지우고 크기 비교로 오름차순 정렬.
    for(int i=0; i<plans.size(); i++) {
        
        // 현재 과제 시작 시각
        int curTime = stoi(plans[i][1].substr(0,2)) * 60
            + stoi(plans[i][1].substr(3,2));
        
        // 현재 과제 완료까지 걸리는 시간
        int curPlayTime = stoi(plans[i][2]);
        
        if(i+1<plans.size()) { // 다음 새로운 과제가 존재하면
            
            // 다음 과제 시작 시각
            int nextTime = stoi(plans[i+1][1].substr(0,2)) * 60
            + stoi(plans[i+1][1].substr(3,2));
            
            // 다음 과제 완료까지 걸리는 시간
            int nextPlayTime =  stoi(plans[i+1][2]);
            
            // 현재 과제가 다음 과제 시작 시각전에 완료가 가능하고 시간이 남는다면
            if(curTime + curPlayTime < nextTime) {
                answer.push_back(plans[i][0]);
                
                // 남은 과제 가능 시간
                int restTime = (nextTime) - (curTime + curPlayTime);
                
                while(!s.empty()) {
                    
                    // 남은 과제를 가능 시간안에 끝낼 수 있다면
                    if(s.top().first<=restTime) {
                        answer.push_back(s.top().second);
                        restTime -= s.top().first;
                        s.pop();
                    } else {
                        // 남은 과제를 완전히 끝내지 못하더라도 남은 시간만이라도 수행
                        string report = s.top().second;
                        int restReportTime = s.top().first;
                        s.pop();
                        s.push(make_pair(restReportTime - restTime, report));
                        break;
                    }
                    
                }
                
                // 다음 과제 시작 시각에 딱 맞춰 현재 과제를 끝냄
            } else if (curTime + curPlayTime == nextTime) {
                answer.push_back(plans[i][0]);
            }
            else { // 현재 과제를 다음 과제 시작전에 다 못 끝냄
                s.push(make_pair( (curTime+curPlayTime) - (nextTime), plans[i][0]));
            }
            
            
        } else { // 마지막 새로운 과제라면 수행하고 멈춰둔 과제들 순서대로 진행
            answer.push_back(plans[i][0]);
            
            while(!s.empty()) { // 멈춰둔 과제들 순서대로 진행
                answer.push_back(s.top().second);
                s.pop();
            }
        }
        
        
        
    }
    
    return answer;