[Programmers] 과제 진행하기

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/176962

프로그래머스

스택을 이용한 시뮬레이션 구현 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 시작 시간을 쉽게 비교하기 위해 시작 시간을 분 단위로 전처리하고 map 자료구조를 통해 해당 시작 시간에 매칭되는 과제를 매핑합니다. 

1.1 이때 가장 빠른 시작 시간도 구해줍니다.

2. 가장 먼저 진행해야 할 과제부터 순차적으로 진행하는데 문제에서 주어진 조건대로 해당 과제를 마무리하기 전 새로운 과제가 나오면 스택에 현재 과제를 넣어주고 새로운 과제를 진행합니다.

2.1 진행하는 과제가 마무리될 때까지 새로운 과제가 안 나올 경우 answer에 현재 진행한 과제의 이름을 넣어주고 멈춰둔 과제가 있을 경우 스택에서 꺼내 마저 진행을 해줍니다.

2.2 시간을 2400 + 100 * 1000까지 진행시킨 이유는 극단적인 edge 케이스를 가정했을 때 1000개의 100분 과제가 모두 23:59에 시작하는 경우가 있을 수 있다고 생각했기 때문입니다.

3. 2번 과정에서 구한 답을 반환합니다.

 

	#include <string>
	#include <vector>
	#include <stack>
	#include <map>
	#include <algorithm>
	#include <iostream>
	using namespace std;
	const int INF = 987654321;
	const string NONE = "";
	typedef struct
	{
	string subject;
	int start;
	int duration;
	} State;
	int getTime(string s)
	{
	return stoi(s.substr(0, 2)) * 60 + stoi(s.substr(3, 2));
	}
	map<int, State> start2state;
	vector<string> solution(vector<vector<string>> plans) {
	int timeStart = INF;
	for (vector<string> plan : plans)
	{
	int start = getTime(plan[1]);
	State state = {plan[0], start, stoi(plan[2])};
	timeStart = min(timeStart, start);
	start2state[start] = state;
	}
	vector<string> answer;
	stack<State> st;
	State cur = start2state[timeStart];
	string subject = cur.subject;
	int start = cur.start;
	int end = cur.start + cur.duration;
	for (int time = timeStart + 1; time < 2400 + 100 * 1000 && answer.size() != plans.size(); time++)
	{
	if (end == time)
	{
	answer.push_back(subject);
	subject = NONE;
	if (!st.empty())
	{
	State state = st.top();
	st.pop();
	subject = state.subject;
	start = time;
	end = time + state.duration;
	}
	}
	if (start2state.count(time))
	{
	if (subject != NONE)
	{
	st.push({subject, time, end - time});
	}
	State state = start2state[time];
	subject = state.subject;
	start = time;
	end = time + state.duration;
	}
	}
	while (!st.empty())
	{
	answer.push_back(st.top().subject);
	st.pop();
	}
	return answer;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE

지적, 조언, 질문 환영합니다! 질문 남겨주세요~