[프로그래머스][C++] 과제 진행하기
과제 진행하기
문제 링크
분석
과제가 시간 순서로 주어지고, 시작 시간이 되면 바로 시작합니다.
이때, 과제를 진행 중에 다음 과제의 시간이 될 경우 현재 과제를 멈추고 새 과제를 시작합니다.
멈추어둔 과제는 새 과제가 끝난 뒤에 다시 이어서 시작합니다.
만약, 멈춘 과제가 한 개가 아니고 여러개라면 가장 최근에 멈춘 과제부터 진행합니다.
모든 과제는 끝까지 마쳐야 하며, 마친 과제를 순서대로 반환해야합니다.
입력 매개변수인 vector<vector<string>> plans는 [name, start, playtime]의 구조로 이루어져 있습니다.
순서대로 과제 이름, 과제 시작 시간, 과제를 마치는데 필요한 시간을 의미하며 분 단위입니다.
과제 이름은 중복이 없고, 모두 소문자이므로 별도의 예외처리는 필요 없을 것 같습니다.
시작 시간을 분으로 변환해서 다루는 것이 계산하기 용이합니다.
시간 순서로 요소가 정렬되어 있지 않기 때문에, 시간 순서로 정렬하여 이용하는 것이 좋습니다.
중단된 과제는 나중에 다시 수행해야 하므로 스택 자료구조를 사용하는 것이 용이합니다.
이때 스택에는 pair<과제 이름, 남은시간>으로 구성하는 것이 좋습니다.
입력된 매개변수를 다음과 같이 변형해서 사용할 수 있습니다.
- 구조체로 만드는 방법
struct Task
{
string name; // 시작 시간
int startTime; // 분 단위로 변환
int playTime; // 과제에 걸리는 시간
};
vector<Task> sortedPlans;
for (const auto& plan : plans)
{
string name = plan[0];
int startTime = toMinutes(plan[1]);
int playTime = stoi(plan[2]);
sortedPlans.push_back({name, startTime, playTime});
}
// 사용 시
string name = sortedPlans[i].name;
int startTime = sortedPlans[i].startTime;
int playTime = sortedPlans[i].playTime;
tuple을 사용하는 방법
vector<tuple<int, string, int>> sortedPlans;
for (const auto& plan : plans)
{
string name = plan[0];
int startTime = toMinutes(plan[1]);
int playTime = stoi(plan[2]);
sortedPlans.emplace_back(startTime, name, playTime);
}
// 사용 시
int startTime = get<0>(sortedPlans[i]);
string name = get<1>(sortedPlans[i]);
int playTime = get<2>(sortedPlans[i]);
pair을 사용하는 방법
vector<pair<int, pair<string, int>>> sortedPlans;
for (const auto& plan : plans)
{
int start = toMinutes(plan[1]);
string name = plan[0];
int playTime = stoi(plan[2]);
sortedPlans.push_back({start, {name, playTime}});
}
// 사용 시
int startTime = sortedPlans[i].first;
string name = sortedPlans[i].second.first;
int playTime = sortedPlans[i].second.second;
풀이
해당 풀이는 vector<vector<string>> plans를 시작 시간으로 정렬하여 사용한 방법입니다.
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <climits>
using namespace std;
// HH:MM 에서 시간을 분 단위 정수로 변환한다.
int timetoMinutes(const string& timeStr)
{
int hour = stoi(timeStr.substr(0, 2));
int minute = stoi(timeStr.substr(3,2));
return hour * 60 + minute;
}
vector<string> solution(vector<vector<string>> plans) {
vector<string> answer;
// 시간 순서로 정렬한다.
sort(plans.begin(), plans.end(), [](const vector<string>& a, const vector<string>& b)
{
return timetoMinutes(a[1]) < timetoMinutes(b[1]);
});
// 밀린 과제를 저장하는 스택 (과제 이름, 남은 시간)
stack<pair<string, int>> remain;
// 과제를 순회한다.
for (int i = 0; i < plans.size(); ++i)
{
// 순서대로 과제 이름, 과제 시작 시간, 과제 소요 시간
string name = plans[i][0];
int startTime = timetoMinutes(plans[i][1]);
int playTime = stoi(plans[i][2]);
// 다음 과제의 시작 시간을 구한다.
// 다음 과제가 없는 경우 최대값을 사용한다.
int nextStartTime = (i + 1 < plans.size()) ? timetoMinutes(plans[i + 1][1]) : INT_MAX;
// 현재 과제의 시작 시간과 다음 과제 시작까지의 시간을 구한다.
int timeGap = nextStartTime - startTime;
// 현재 과제를 다 끝낼 수 있는 경우
if (playTime <= timeGap)
{
// 현재 과제를 끝낼 수 있으므로 반환 값에 추가
answer.push_back(name);
// 현재 과제를 끝내고 남은 시간을 구한다.
timeGap -= playTime;
// 남은 시간 동안 수행해야하는 이전 과제가 있는 경우
while (!remain.empty() && 0 < timeGap)
{
// 가장 최근에 멈춘 과제의 이름과 남은 시간을 가져온다.
auto [remainName, remainTime] = remain.top();
remain.pop();
// 가장 최근에 남은 과제를 끝낼 수 있는 경우
if (timeGap >= remainTime)
{
// 현재 과제를 끝내고 남은 시간을 갱신한다.
timeGap -= remainTime;
// 과제를 끝냈으므로 반환 값에 추가
answer.push_back(remainName);
}
else
{
// 가장 최근에 남은 과제를 끝낼 수 없는 경우이므로, 남은 시간을 갱신해서 다시 스택에 추가
remain.push({remainName, remainTime - timeGap});
break;
}
}
}
else
{
// 이 코드에 온 경우 다음 과제를 시작해야하는 시간까지 다 못끝냈다는 의미다.
// 멈추고, 남은 시간으로 저장한다.
remain.push({name, playTime - timeGap});
}
}
return answer;
}
성능 요약
시간 복잡도는$O(n \ log \ n)$입니다.
- 정렬 함수 $O(n \ log \ n)$
- 과제를 순회하는 반복문 $O(n)$
- 이전 과제를 이어서 수행하는 반복문 $O(n)$
- $O(n \ log \ n) + O(n) + O(n)$
공간 복잡도는 $O(n)$입니다.
- 결과 값을 저장하는
vector<string> answer$O(n)$ - 밀린 과제를 저장하는 스택
stack<pair<string, int>> remain$O(n)$ - $O(n) + O(n)$
테스트 성능
테스트 1 〉 통과 (0.02ms, 4.44MB)
테스트 2 〉 통과 (0.02ms, 4.14MB)
테스트 3 〉 통과 (0.02ms, 4.17MB)
테스트 4 〉 통과 (0.04ms, 3.68MB)
테스트 5 〉 통과 (0.04ms, 3.61MB)
테스트 6 〉 통과 (0.05ms, 3.68MB)
테스트 7 〉 통과 (0.09ms, 4.21MB)
테스트 8 〉 통과 (0.08ms, 4.02MB)
테스트 9 〉 통과 (0.17ms, 3.75MB)
테스트 10 〉 통과 (0.17ms, 4.19MB)
테스트 11 〉 통과 (0.33ms, 4.21MB)
테스트 12 〉 통과 (0.93ms, 4.2MB)
테스트 13 〉 통과 (0.97ms, 4.14MB)
테스트 14 〉 통과 (1.87ms, 4.19MB)
테스트 15 〉 통과 (1.87ms, 4.13MB)
테스트 16 〉 통과 (0.01ms, 3.73MB)
테스트 17 〉 통과 (0.02ms, 4MB)
테스트 18 〉 통과 (0.01ms, 4.2MB)
테스트 19 〉 통과 (0.02ms, 4.21MB)
테스트 20 〉 통과 (0.16ms, 4.16MB)
테스트 21 〉 통과 (0.16ms, 4.21MB)
테스트 22 〉 통과 (2.98ms, 4.21MB)
테스트 23 〉 통과 (2.18ms, 4.11MB)
테스트 24 〉 통과 (1.82ms, 4.2MB)
댓글남기기