프로그래머스 과제 진행하기

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

프로그래머스

 

문제접근법 : 

단순 구현문제인데  그 구현을 어떻게 하냐에 달려있습니다. 시간이 짧기때문에 배열로 장황해서 2000까지 주면서

풀수도 있고 빠르게 풀고싶다면 현재 시간과 다음시간의 텀이 얼마인지 확인한후 그텀의 시간만으로 못미룬 과제까지 해결할수 있다면 해결하고 해결하지못한다면 계속미루는겁니다.

 

핵심은

• 멈춰둔 과제가 여러 개일 경우, 가장 최근에 멈춘 과제부터 시작합니다.

이거 보자마자 스택을 떠오르면 쉽게풀수있는문제 인데 알고리즘 문제 요새 정말 오랜만에 풀어서그런지

구상은 잘했어도 알고리즘 짜는데 1시간 걸렸네요 와... 이게 정말 알고리즘 쉬었던게 정말 무섭네요..

 

소스코드 :

#include<bits/stdc++.h>
using namespace std;
int totime(string &s){
    return stoi(s.substr(0,2))*60+stoi(s.substr(3,2));
}

vector<string> solution(vector<vector<string>> plans) {
    vector<string> answer;
    vector<tuple<int,int,string>> v,st;
    for(vector<string>&t :plans){
        v.push_back({totime(t[1]),stoi(t[2]),t[0]});
    }
    sort(v.begin(),v.end());
    int before,bdelay;
    string bname;
    st.push_back(v[0]);
    for(int i=1;i<v.size();i++){
        int cur,delay;
        string name;
        tie(cur,delay,name)=v[i];
        int term = cur - get<0>(v[i-1]);
        while(!st.empty()&&term>0){
            tie(before,bdelay,bname) = st.back();
            st.pop_back();
            bdelay -=term;
            if(bdelay>0){
                term=0;
                st.push_back({before,bdelay,bname});
            }
            else{
                term=-bdelay;
                answer.push_back(bname);
            }
        }
        st.push_back(v[i]);
    }
    while(!st.empty()){
        answer.push_back(get<2>(st.back()));
        st.pop_back();
    }
    return answer;
}

 

 

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.