프로그래머스. 과제 진행하기 (스택, 구현)

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

프로그래머스

풀이법을 떠올리기는 어렵지 않은데, 구현이 복잡하다. 

1. 특징

1) 스택을 사용한 구현

 

2. 구현 방식

1) 날짜(월:일)혹은 시간(시:분)으로 주어진 경우 월*30 + 일, 시 * 60 + 분 등으로 계산하여, 단위를 각각 일, 분으로 맞춰준다. 

해당 문제에서 시:분으로 과제 시작시간이 들어오기 때문에 12:10로 들어온 시간을 12*60 + 10으로 계산했다. 

2) plans 벡터를 들어온 시간 순으로 정렬하기 위해,

새로운 벡터 vector<tuple<int, int, string>> _p; // start(12:10 -> 12*60+10), playtime, name

을 선언하고 오름차순 정렬해준다. 

3) 현재 과제를 하던 도중, 다른 과제가 들어왔을 때, 다른 과제를 먼저 처리해야한다. 

다음 과제가 들어오기 전에, 현재 과제를 다해서 시간이 남으면, 이전 과제를 해야하는데, 이 계산을 위해

stack<pair<int, string>> s; //남은 시간, 이름

을 사용한다. 

 

if(현재시간(start)+ 현재 과목을 끝내는 데 걸리는 시간(playtime) > 다음 과제가 들어온 시간(start))

   stack.push({현재 과목을 끝내기 위해 남은 시간, 현재 과목 이름});

else // 시간이 남은 경우

   stack을 순회하면서, stack의 top부터 과제를 한다. 남은 시간이 없으면, 스택의 순회를 멈춘다. 

위의 if-else는 처음부터 n-2까지의 과제를 하는 방법이다. 

n-1은 본인 과제를 하고, stack의 남은 순서대로 pop 하면된다. 

 

 

3. 코드

#include <bits/stdc++.h>

using namespace std;
vector<tuple<int, int, string>> _p;
stack<pair<int, string>> s; //남은 시간, 이름
void split(int idx, string& start, string& name, string& playtime)
{
    string tmp = "";
    int h = 0;
    int m = 0;
    for(int i = 0; i < start.size(); i++)
    {
        if(start[i] == ':')
        {
             h = stoi(tmp);
             tmp = "";
        }
        else
        {
            tmp += start[i];
        }
    }
    m = stoi(tmp);
    _p.push_back(make_tuple(h * 60 + m, stoi(playtime), name));
}

vector<string> solution(vector<vector<string>> plans) {
    vector<string> answer;
    int n = plans.size();
    
    // start시간을 분으로 바꿔서 오름차순 정렬
    for(int i = 0; i < n; i++)
    {
        split(i, plans[i][1], plans[i][0], plans[i][2]);
    }
    
    sort(_p.begin(), _p.end());
    
    for(int i = 0; i < n; i++)
    {
        if(i == n-1)
        {

                answer.push_back(get<2>(_p[i]));
                while(!s.empty())
                {
                    answer.push_back(s.top().second);
                    s.pop();
                }
        }
        else
        {
            if(get<0>(_p[i]) + get<1>(_p[i]) > get<0>(_p[i+1]))
            {
                int rem = get<1>(_p[i]) - (get<0>(_p[i+1]) - get<0>(_p[i]));
                s.push(make_pair(rem, get<2>(_p[i])));
            }
            else
            {

                answer.push_back(get<2>(_p[i]));
                int re = get<0>(_p[i+1]) - (get<0>(_p[i]) + get<1>(_p[i]));

                while(!s.empty()) 
                {
                    int topremain = s.top().first - re;
                    string topname = s.top().second;
                    if(topremain <= 0)
                    {
                        re = re - s.top().first;
                        answer.push_back(s.top().second);
                        s.pop(); 
                    }
                    else
                    {
                        s.pop();
                        s.push(make_pair(topremain, topname));
                        break;
                    }

                }
            }
        }

    }
    
    return answer;
}