[프로그래머스 C++] 과제 진행하기

 

 

[프로그래머스 C++] 과제 진행하기

 

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

---

 

해결전략

 

문자열

자료구조 스택 stack

---

 

 

정답코드

 

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
 
struct Info { // 과제 정보를 담는 구조체 정의
    string subject; int time, duration;
 
    Info(string a, int b, int c) {
        subject = a;
        time = b;
        duration = c;
    }
    
    bool operator<(const Info& oper) const{
        return time < oper.time; // 시작 시간을 기준으로 오름차순 정렬
    }
};
 
vector<string> solution(vector<vector<string>> plans) {
    int n = plans.size();  // 전체 과제의 수
    vector<string> answer; // 최종 과제 수행 순서를 담을 벡터
    vector<Info> v;        // 과제 정보를 담을 벡터
    stack<Info> st;        // 시간 내에 끝내지 못한 과제를 임시 저장할 스택
 
    for (int i = 0; i < n; i++) // 문자열로 주어진 과제 정보를 파싱하여 벡터에 저장
    {
        string subject = plans[i][0];
        string time = plans[i][1];
        string duration = plans[i][2];
        int t = stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3, 5)); // 분 단위
        int dur = stoi(plans[i][2]);
 
        v.push_back({ subject, t, dur });
    }
    sort(v.begin(), v.end());  // 시작 시간 기준으로 과제 정렬
 
    for (int i = 1; i < n; i++)
    {
        if (v[i - 1].time + v[i - 1].duration <= v[i].time) // 이전 과제와 현재 과제 사이에 시간적 여유가 있는 경우
        {
            answer.push_back(v[i - 1].subject);
 
            int leftTime = v[i].time - (v[i - 1].time + v[i - 1].duration);
            
            while (leftTime && !st.empty()) // 스택에 남아있는 과제를 시간적 여유를 바탕으로 처리
            {
                if (leftTime >= st.top().duration) {
                    leftTime -= st.top().duration;
                    answer.push_back(st.top().subject);
                    st.pop();
                }
                else { // leftTime < Q.front().duration
                    st.top().duration -= leftTime;
                    leftTime = 0;
                }
            }
        }
        else // 시간적 여유가 없는 경우, 과제를 스택에 저장
        { 
            v[i - 1].duration -= (v[i].time - v[i - 1].time);
            st.push({ v[i - 1].subject, v[i - 1].time, v[i - 1].duration });
        }
 
        if (i == n - 1) { // 맨 마지막 과제 소요 시간과 상관없이 끝낸다
            answer.push_back(v[i].subject);
        }
    }
 
    while (!st.empty()) // 아직 끝내지 못한 과제를 순차적으로 끝냄
    {
        answer.push_back(st.top().subject);
        st.pop();
    }
 
    return answer;
}
 
int main() {
    vector<vector<string>> testcase1 = { {"korean", "11:40", "30"}, {"english", "12:10", "20"},{"math", "12:30", "40" } };
    vector<vector<string>> testcase2 = { {"science", "12:40", "50"}, {"music", "12:20", "40"}, {"history", "14:00", "30"}, {"computer", "12:30", "100"} };
    vector<vector<string>> testcase3 = { {"aaa", "12:00", "20"}, {"bbb", "12:10", "30"}, {"ccc", "12:40", "10"} };
    vector<vector<string>> testcase4 = { {"aaa", "12:00", "30"}, {"bbb", "12:10", "30"}, {"ccc", "14:00", "30"} };
 
    solution(testcase1); // "korean", "english", "math"
    solution(testcase2); // "science", "history", "computer", "music"
    solution(testcase3); // "bbb", "ccc", "aaa"
    solution(testcase4); // "bbb", "aaa", "ccc"
 
    return 0;
}

 

 

---