[프로그래머스] 과제 진행하기 (c++)

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

프로그래머스

[문제 요약]

과제 배열(name, start, playtime)에 대해 먼저 끝나는 과제 순서대로 스케쥴링 하는 문제이다.

 

 

[풀이]

• 정렬, 자료구조, 시뮬레이션, 구현 문제 O(NlogN)에 해결된다.
• 과제배열의 시작 시간은 정렬되어 있지 않기 때문에 시작시간을 기준으로 정렬한다.
• 다음 과제의 시작 시간과 현재 과제가 끝나는 시간을 비교해야 한다.
  • nextStart - (curStart + playTime) 은 과제 후 남은 시간(freeTime)이 된다.
  • freeTime >= 0 : 과제를 끝내고 남는 시간
    따라서, freeTime동안 끝내지 못했던 과제를 수행한다.
  • freeTime < 0 : 과제를 끝내지 못하고, 과제를 마저 해결하기 위한 시간
    따라서, 현재의 과제를 schedule에 이름과 남은 시간으로 추가(LIFO이기에 stack)한다.

 

 

[코드]

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

using namespace std;

stack<pair<string, int>> s;

int freeTime(string s, string r, string n) {
	auto startTime = stoi(s.substr(0, 2)) * 60 + stoi(s.substr(3, 5));
	auto runTime = stoi(r);
	auto nextStartTime = stoi(n.substr(0, 2)) * 60 + stoi(n.substr(3, 5));
	
	return nextStartTime - (startTime + runTime);
}

vector<string> solution(vector<vector<string>> plans) {
	vector<string> answer;
	int sz = plans.size();

	sort(plans.begin(), plans.end(), [](vector<string> &p1, vector<string> &p2) {
		return p1[1] < p2[1];
	});

	for (int i = 0; i < sz - 1; i++) {
		auto freeMinute = freeTime(plans[i][1], plans[i][2], plans[i + 1][1]);
		if (freeMinute < 0) {
			s.push({ plans[i][0], -freeMinute });
		}
		else {
			answer.push_back(plans[i][0]);
			while (freeMinute && !s.empty()) {
				auto &task = s.top();
				if (task.second > freeMinute) {
					task.second -= freeMinute;
					freeMinute = 0;
				}
				else {
					answer.push_back(task.first);
					freeMinute -= task.second;
					s.pop();
				}
			}
		}
	}

	answer.push_back(plans[sz - 1][0]);

	while (!s.empty()) {
		answer.push_back(s.top().first);
		s.pop();
	}

	return answer;
}

 

[코드 설명]

시간과 분으로 나눠서 코드를 작성하면 가독성이 떨어지기에 분으로 통일하여 표현한다.

s.top() 함수는 shallow copy가 아니므로 reference로 받아야 stack top의 value도 바뀐다.