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

문제

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

프로그래머스

 

---

 

코드

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

using namespace std;

int cmp(vector<string>a, vector<string>b)
{
    return a[1]<b[1];
}

vector<string> solution(vector<vector<string>> plans) {
    vector<string> answer;
    sort(plans.begin(), plans.end(), cmp);
    stack<pair<string, int>> s;
    int cur_time = stoi(plans[0][1].substr(0, 2))*60+stoi(plans[0][1].substr(3,2));
    for(int i=0;i<plans.size();i++)
    {
        int temp = stoi(plans[i][1].substr(0, 2))*60+stoi(plans[i][1].substr(3,2));
        while(!s.empty())
        {
            int m = s.top().second;
            if(temp>=cur_time+m)
            {
                cur_time+=m;
                answer.push_back(s.top().first);
                s.pop();
            }
            else
            {
                pair<string, int> tmp_pair = s.top();
                s.pop();
                s.push(make_pair(tmp_pair.first, tmp_pair.second-(temp-cur_time)));
                break;
            }
        }
        if(i==plans.size()-1){
            answer.push_back(plans[i][0]);
            break;
        }
        cur_time=temp;
        int next_time = stoi(plans[i+1][1].substr(0, 2))*60+stoi(plans[i+1][1].substr(3,2));
        int m = stoi(plans[i][2]);
        string plan = plans[i][0];
        if(next_time>=cur_time+m)
        {
            cur_time+=m;
            answer.push_back(plan);
        }
        else
        {
            s.push(make_pair(plan, m-(next_time-cur_time)));
            cur_time=next_time;
        }
    }
    while(!s.empty())
    {
        answer.push_back(s.top().first);
        s.pop();
    }
    return answer;
}

 

---

 

풀이

오늘도 자괴감 max인 상태로 내 코드 풀이를 진행해보자

 

우선 시간순으로 일을 진행해야 하므로 algorithm 헤더의 sort를 사용하여 plans를 시간순으로 정렬한다.

 

도중에 멈춘 일 중 최근에 멈춘 일을 수행해야 하기 때문에 stack을 선언해준다.

string 인자 값은 과제의 이름, int는 남은 시간을 의미한다.

 

 

시간을 편히 보기 위해 시*60+분으로 변환해준다.

그 뒤 plans를 순회하면서 과제를 수행하자.

 

 

과제를 시작하기로 한 시간이 오기 전에 도중에 멈춘 과제가 있다면 시작 시간 전까지 수행해주도록 한다.

시간이 오기 전까지 과제를 끝낼 수 있으면(if(temp>=cur_time+m)) 계속 stack에서 pop하면서 과제들을 최근 멈춘 순으로 해결해준다. 다 끝내면 answer에 push_back

만약 과제를 끝내기까지 시간이 모자라다면 과제를 한 만큼만 시간을 감소한다.

 

 

만약 일정이 과제 하나밖에 남지 않았다면 그 과제를 끝낸다.(answer.push_back)

 

 

만약 일정에 과제가 여러 개 남아있다면 일을 수행하되, 다음 시작시간이 올 때까지 끝낼 수 있다면(if(next_time>=cur_time+m)) 과제를 다 끝내도록 한다.

만약 다 끝낼수 없다면 할 수 있을만큼만 하고 과제와 남은 시간 값 한 쌍을 stack에 push해준다.

 

 

일정이 끝났음에도 할 일이 남아있다면 최근 멈춘 과제인 stack의 top부분부터 차례로 수행하면서 pop해준다.

 

 

분명 코드를 좀 더 깔끔하게 할 수 있을 것 같은데(있어야만 할 정도로 심각하다) 내 실력의 한계는 여기까지인걸로...

갈수록 코딩 실력이 퇴화하는 것 같다...

 

---

 

다른 사람 풀이

오늘도 어김없이 대단한 분들의 풀이를 보며 모자란 나의 코드 실력을 반성해보자

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

using namespace std;

bool comp (vector<string> a, vector<string> b) {
    return a[1] < b[1];
}

int getTime (string s) {
    int h = stoi(s.substr(0, 2));    
    int m = stoi(s.substr(3));
    return h * 60 + m;
}

vector<string> solution(vector<vector<string>> plans) {
    sort(plans.begin(), plans.end(), comp);


    unordered_map<string, int> m;
    for (vector<string> plan : plans) m[plan[0]] = stoi(plan[2]);

    stack<vector<string>> st;
    st.push(plans[0]);

    int idx = 1;
    int time = getTime(plans[0][1]);

    vector<string> answer;
    while (!st.empty()) {
        time++;
        string sub = st.top()[0];
        m[sub]--;

        if (m[sub] == 0) {
            st.pop();
            answer.push_back(sub);
        }

        if (idx < plans.size() && (time == getTime(plans[idx][1]) || st.empty())) {
            st.push(plans[idx]);
            time = getTime(plans[idx][1]);
            idx++;
        } 
    }
    return answer;
}

 

하고 있는 일들 다 스택에 넣는 case

어쩐지 내 코드를 더 줄일 수 있을 것 같더라니 이런 방식 때문인 모양...

 

map을 사용하여 과제 이름을 key, 남은 시간을 value로 저장한다.

plan에 있는 과제를 스택에 push하고 스택이 비어있지 않은 동안 스택 top에 위치한 과제의 남은 시간을 줄이고 흘러간 시간은 늘린다.(time++, m[sub]--)

만약 과제를 다 끝냈다면(m[sub]==0) 스택에서 과제를 pop하고 answer에 push_back

만약 일정이 남은 상태에서 일정 시작 시간이 되거나 시작 시간이 오기 전 해야 할 과제들을 다 끝낸 경우 다음 일정을 시작한다.

 

이를 스택이 빌 때까지, 즉 과제를 끝낼때까지 계속 반복해주면 끝!

 

 

잘하는 사람들 보면 참 부럽다... 나는 언제쯤...?ㅎ