[Programmers] 과제 진행하기

프로그래머스

 

1. 구현 아이디어

먼저, 시간 순서에 따라 과제를 진행해야 하므로 plans 배열을 시작 시각 순으로 정렬한다.

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

    return false;
}

 

 

입출력 예제에 있는 표를 통해 잠시 멈춘 과제를 스택으로 구현해야 한다는 힌트를 얻을 수 있었다. (최근에 멈춘 과제를 먼저 하므로, 선입후출)

 

이제 plans 배열을 돌며 진행 중인 과제가 끝나는 시각(endTime)과 다음 과제 시작 시각(nextStartTime)을 비교하며 스택 또는 answer 배열(과제를 끝낸 순서대로 이름이 들어있는 배열)에 원소를 삽입해주어야 한다.

 

구체적인 과정은 아래와 같다.

• endTime == nextStartTime: answer 배열에 진행 중인 과제 이름을 삽입하고, 다음 과제를 진행한다.
• endTime > nextStartTime: 진행 중인 과제를 잠시 멈추고, 다음 과제를 먼저한다.
  • 스택에 {과제 이름, 남은 시간} 삽입
• endTime < nextStartTime: 다음 과제까지 시간 여유(breakTime)가 있다는 뜻. 남은 시간동안 스택에 있는 과제를 해결한다
  • breakTime = nextStartTime - endTime
  • 남은 시간이 0 이하거나 스택에 남은 과목이 존재하지 않을 때까지 반복해서 과제를 해결한다
    • leftTime = 해당 과목을 끝낼 때까지 남은 시간 → top().second
    • breakTime < leftTime: 쉬는 시간을 전부 사용했지만, 해당 과목을 끝내지 못함
    • breakTime >= leftTime: 해당 과목을 스택에서 pop하고 다음 과목 해결
    • 글로 이해가 안된다면 아래 그림을 참고하자!

breakTime과 leftTime을 비교

 

 

위 로직을 처리하기 위해서는 시작 시각과 소요 시간으로 끝나는 시각을 계산해야 한다.

끝나는 시각을 계산하는 함수는 아래와 같다.

 

이 때, 주의해야 할 점이 hh:mm 포맷이므로 숫자가 두 자리가 아닐 경우(10 이하일 경우) 앞에 0을 붙여주어야 한다.

(이것을 지키지 않아 core dumped 에러 계속 발생했음 ㅠㅠ)

string getEndTime(vector<string> plan) {
    string startTime = plan[1];
    string playTime = plan[2];

    int hour = stoi(startTime.substr(0, 2));
    int minute = stoi(startTime.substr(3, 2));

    minute += stoi(playTime);

    hour += minute / 60;
    minute %= 60;

    string hourString = (hour < 10) ? "0" + to_string(hour) : to_string(hour);
    string minuteString = (minute < 10) ? "0" + to_string(minute) : to_string(minute);
    return hourString + ":" + minuteString;
}

 

그리고 시각 간 차이를 비교하는 함수도 필요하므로 아래와 같이 구현하였다.

int getLeftTime(string a, string b) { // b가 a보다 먼저
    int ah = stoi(a.substr(0, 2));
    int am = stoi(a.substr(3, 2));

    int bh = stoi(b.substr(0, 2));
    int bm = stoi(b.substr(3, 2));

    return (ah * 60 + am) - (bh * 60 + bm);
}

 

시각을 분으로 치환하여 계산하였으며, 반환값도 분 단위이다.

 

2. 전체 코드

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

using namespace std;

// 과제 시작 시각을 기준으로 정렬
bool comp(vector<string> a, vector<string> b) {
    if (a[1] < b[1]) return true;

    return false;
}

string getEndTime(vector<string> plan) {
    string startTime = plan[1];
    string playTime = plan[2];

    int hour = stoi(startTime.substr(0, 2));
    int minute = stoi(startTime.substr(3, 2));

    minute += stoi(playTime);

    hour += minute / 60;
    minute %= 60;

    string hourString = (hour < 10) ? "0" + to_string(hour) : to_string(hour);
    string minuteString = (minute < 10) ? "0" + to_string(minute) : to_string(minute);
    return hourString + ":" + minuteString;
}

int getLeftTime(string a, string b) { // b가 a보다 먼저
    int ah = stoi(a.substr(0, 2));
    int am = stoi(a.substr(3, 2));

    int bh = stoi(b.substr(0, 2));
    int bm = stoi(b.substr(3, 2));

    return (ah * 60 + am) - (bh * 60 + bm);
}

vector<string> solution(vector<vector<string>> plans) { // [name, start, playtime]
    vector<string> answer;

    // 1. plans를 start를 기준으로 정렬한다
    sort(plans.begin(), plans.end(), comp);

    stack<pair<string, int>> stopped; // 잠시 멈춘 과제 {과목 이름, 남은 시간}

    // 2. plans를 돌며 과제 진행
    for (int i = 0; i < plans.size(); i++) {
        if (i == plans.size() - 1) { // 마지막 과제일 경우
            answer.push_back(plans[i][0]);
            // 멈추지 않고 남은 과제 계속 진행
            while (!stopped.empty()) {
                answer.push_back(stopped.top().first);
                stopped.pop();
            }

            break;
        }

        string endTime = getEndTime(plans[i]); // 현재 과목 마치는 시각
        string nextStartTime = plans[i+1][1]; // 다음 과목 시작 시각

        if (endTime == nextStartTime) { // 바로 다음 과목 시작
            answer.push_back(plans[i][0]);
        } else if (endTime > nextStartTime) { // 잠시 멈추고 다음 과제 먼저
            stopped.push({plans[i][0], getLeftTime(endTime, nextStartTime)});
        } else { // endTime < nextStartTime, 남은 시간동안 스택에 쌓인 과제 진행
            answer.push_back(plans[i][0]);

            // 다음 과목 시작까지 남은 시간 계산
            int breakTime = getLeftTime(nextStartTime, endTime);

            while (breakTime > 0 && !stopped.empty()) {
                string name = stopped.top().first; // 과목명
                int leftTime = stopped.top().second; // 해당 과목 남은 시간

                if (breakTime < leftTime) { // 남은 시간을 모두 사용 but 다 못 끝냄
                    stopped.top().second -= breakTime;
                    breakTime = 0;
                } else { // breakTime >= leftTime
                    breakTime -= leftTime;
                    answer.push_back(name);
                    stopped.pop();
                }
            }
        }
    }

    return answer;
}