[프로그래머스 C++] - 기능 개발

문제 : 기능 개발

 

https://programmers.co.kr/learn/courses/30/lessons/42586

 

 분석

 조건이 간결하다.

 

1. 매일 개발이 진행된다.

2. 배포는 앞에서부터 이뤄진다.

 

처리 순서를 반복문을 통해 간단하게 구현할 수 있다.

vector<int> solution(vector<int> progresses, vector<int> speeds) 
{
	vector<int> answer;
	while (true)
	{
		// base case
		if (progresses.size() == 0) break;
		else if (progresses.size() == 1)
		{
			answer.push_back(1);
			break;
		}

		// progresses
		for (size_t i = 0; i < progresses.size(); i++)
		{
			progresses[i] += speeds[i];
		}

		// 배포
		if (progresses.front() >= 100)
		{
			int cnt = 0;
			vector<int> tmp = progresses;
			for (size_t i = 0; i < tmp.size(); i++)
			{
				if (tmp[i] >= 100)
				{
					progresses.erase(progresses.begin());
					speeds.erase(speeds.begin());
					cnt++;
				}
				else break;
			}
			answer.push_back(cnt);
		}
	}

	return answer;
}

 

 최적화

 좀 더 생각해보면, 기능별로 개발 완료되는 시간이 이미 정해져 있다. 뒤 기능들이 개발하는 데 짧게 걸려도 앞선 기능들이 개발이 안 끝났으면 배포를 못한다. 이를 기준으로 코드를 짜면 반복문 한 번으로 처리가 가능하게 된다!!

 

vector<int> solution(vector<int> progresses, vector<int> speeds) 
{
	vector<int> answer;

	int day, max_day = 0;
	for (int i = 0; i < progresses.size(); i++)
	{
		day = (99 - progresses[i]) / speeds[i] + 1;

		if (answer.empty() || max_day < day)
		{
			answer.push_back(1);
		}
		else
		{
			++answer.back();
		}

		if (max_day < day)
		{
			max_day = day;
		}
	}

	return answer;
}