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

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

using namespace std;

//시간을 분으로 저장
struct goodPlan
{
    string name;
    int time;
    int playTime;
};

//시간순으로 정렬
bool sortPlans(goodPlan a, goodPlan b)
{
    if (a.time < b.time)
    {
        return true;
    }

    return false;
}

vector<string> solution(vector<vector<string>> plans) {
    vector<string> answer;
    vector<goodPlan> resultPlan;
	
    //분으로 치환한 값을 넣어놓는다.
    for (int i = 0; i < plans.size(); ++i)
    {
        string time = "";
        time += plans[i][1][0];
        time += plans[i][1][1];
        string minute = "";
        minute += plans[i][1][3];
        minute += plans[i][1][4];

        int resultTime = stoi(time) * 60 + stoi(minute);
        resultPlan.push_back({ plans[i][0], resultTime, stoi(plans[i][2]) });
    }

    sort(resultPlan.begin(), resultPlan.end(), sortPlans);

    string currName = resultPlan[0].name;
    int currTime = resultPlan[0].time;
    int currPlayTime = resultPlan[0].playTime;

	//멈춘 과제들 저장
    stack<pair<string, int>> remainPlan;

    for (int i = 1; i < resultPlan.size(); ++i)
    {
        string nextName = resultPlan[i].name;
        int nextTime = resultPlan[i].time;
        int nextPlayTime = resultPlan[i].playTime;

        //다음 시간보다 적은 시간내에 끝냈다면 멈춘 과제 불러온다.
        if (currTime + currPlayTime < nextTime)
        {
            answer.push_back(currName);

            //현재 시간을 추가하고 저장된 값을 가져온다.
            currTime += currPlayTime;

            if (!remainPlan.empty())
            {
                currName = remainPlan.top().first;
                currPlayTime = remainPlan.top().second;
                remainPlan.pop();
                --i;
            }
            else
            {
                currName = nextName;
                currTime = nextTime;
                currPlayTime = nextPlayTime;
            }
        }
        //다음 시간과 같은 시간에 끝났다면 바로 다음 시간을 가져온다.
        else if (currTime + currPlayTime == nextTime)
        {
            answer.push_back(currName);
            currName = nextName;
            currTime = nextTime;
            currPlayTime = nextPlayTime;
        }
        //다음 시간내에 과제를 못 끝내면 남은 시간을 저장한다.
        else
        {
            remainPlan.push({ currName, currTime + currPlayTime - nextTime });
            currName = nextName;
            currTime = nextTime;
            currPlayTime = nextPlayTime;
        }
    }

    answer.push_back(currName);

    //멈춘 과제 소환!
    while (!remainPlan.empty())
    {
        answer.push_back(remainPlan.top().first);
        remainPlan.pop();
    }

    return answer;
}

 

문제 풀이

1. 분으로 치환해서 값을 저장하고 시간순으로 정렬해준다.

2. 첫번째 과제(현재 과제)을 저장하고 다음 과제부터 계산해준다.

3. 다음 과제 시작 시간보다 현재 과제 끝날 시간이 적을 경우, 멈춘 과제가 있다면 멈춘 과제를 불러온다.

4. 다음 과제 시작 시간과 현재 과제 끝날 시간이 동일할 경우 다음 과제를 불러온다.

5. 다음 과제 시작 시간보다 현재 과제 끝날 시간이 초과할 경우, 멈춘 과제에 저장해놓고 다음 과제를 불러온다. 이 때 멈춘 과제는 최근 순으로 하기 위해 Stack을 사용해준다.

6. 마지막 과제까지 도달했다면 마지막 과제와 남은 과제를 모두 해결해준다.

 

풀면서 느낀점

1. 자칫하면 변수들이 복잡해지므로 잘 정리하면서 풀어야겠다.

2. 여러개를 한번에 할 생각 말고 하나씩 차근차근 적어가면서 풀어야겠다.

3. 웬만한 시간이 나오는 문제는 분이나 초로 계산하기 쉽게 만든 후에 푸는 것이 좋아보인다.

 

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

프로그래머스