기능개발 Programmers 프로그래머스 C++

다음 링크를 통해서 해당 문제를 보실 수 있습니다.
programmers.co.kr/learn/courses/30/lessons/42586

코딩테스트 연습 - 기능개발

문제 설명

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한 사항

• 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
• 작업 진도는 100 미만의 자연수입니다.
• 작업 속도는 100 이하의 자연수입니다.
• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

입출력 예

progresses	speeds	return
[93, 30, 55]	[1, 30, 5]	[2, 1]
[95, 90, 99, 99, 80, 99]	[1, 1, 1, 1, 1, 1]	[1, 3, 2]

입출력 예 설명

입출력 예 #1
첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다.
두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다.
세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다.

따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.

입출력 예 #2
모든 기능이 하루에 1%씩 작업이 가능하므로, 작업이 끝나기까지 남은 일수는 각각 5일, 10일, 1일, 1일, 20일, 1일입니다. 어떤 기능이 먼저 완성되었더라도 앞에 있는 모든 기능이 완성되지 않으면 배포가 불가능합니다.

따라서 5일째에 1개의 기능, 10일째에 3개의 기능, 20일째에 2개의 기능이 배포됩니다.

구현

우선 모든 기능이 배포되기 위해서는 순서대로 작업된다는 것에 유념해야 한다.
다음번에 들어오는 기능이 완료됐다고 하더라도 무조건 그 전에 있던 기능이 완료되는 시점에서 같이 배포가 완료된다는 것을 기억을 하고 코드를 짜기 시작해야한다.

나는 두가지 정도의 방법이 떠올랐다.

1. progresses와 speeds의 각각의 인덱스마다 100이 될때까지의 배포날짜를 각각 구해서 새로운 벡터에 저장해준 후 해당 벡터를 돌면서 숫자가 커지기전까지 cnt를 추가해주며 숫자가 커질경우 해당 cnt를 answer에 추가해주고 cnt를 0으로 초기화시켜주는 방법이 있다.
2. progresses를 쭉 돌면서 speed를 각 인덱스마다 날짜를 구해주며 해당 숫자를 저장해둔 후 다음 번 인덱스의 날짜가 이전 값보다 크면 새롭게 answer에 추가해주고 아닐경우 원래 answer에 추가해주는 방법이 있다.

여기서 나는 2번의 방법을 통하여 코드를 구현하였다.

cnt = 0;	// 해당 기능이 배포될 때 까지의 날짜
while (progresses[i] < 100) {
	progresses[i] += speeds[i];
	cnt++;
}

• 위와 같은 코드를 통해서 각 기능이 배포될 때 까지의 최소한의 일 수를 구한다.

if (i == 0) {			// 첫번째 들어온 값은 무조건 추가
	temp.push_back(cnt);	// 다음에 들어올 값과 비교하기 위하여 저장해줌. vector 사용안해도됨.
	answer.push_back(1);	
	answer_index = 0;	// 다음 들어올 값이 어디에 들어올 지 모르므로 index 사용
}

• 이후 첫번째 배포되는 기능은 무조건 answer vector에 추가한다.
  즉 첫번째 기능이 배포되는 날짜(cnt)를 answer의 첫번째 index에 추가하는 것이다.
  또한 다음번에 들어온 기능의 배포까지의 날을 비교하기 위하여 날짜를 temp vector에 따로 추가해준다.
• 다음 번에 들어올 기능이 배포되는 날짜는 첫번째 들어오는 기능보다 먼저 완료되었다고 하더라도 해당날짜와 같은 날에 배포가 될 수 있기에 answer의 해당 인덱스에 추가 해주어야 하기에 answer_index를 그대로 0으로 유지한다.

else {
	if (cnt <= temp.back()) {	// 새로 들어온 날짜가 기존 보다 작을 경우
		answer[answer_index]++;
	}
	else {				// 새로 들어온 날짜가 기존 보다 클 경우
		temp.push_back(cnt);
		answer.push_back(1);
		answer_index++;		// 인덱스를 늘리는 것을 까먹으면 안된다.
	}
}

• 다음 번부터 완료되는 작업들은 만약 배포될때까지의 날짜가 이미 vector에 들어온 날짜보다 빠르다면 이미 앞서 배포된 날짜에 해당 기능이 배포되도록 추가해준다.(answer_index는 그대로 고정)
• 만약 해당 날짜가 이미 vector에 있는 값보다 느리다면 1번째 값이 들어왔을때와 같은 과정을 수행한다.
  즉 비교해줄 temp에 새로운 값을 넣어주고 answer vector에 새로운 1을 추가해주고 answer_index를 추가해준다.

전체 코드는 아래에서 볼 수 있다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    vector<int> temp(1);
    int len = progresses.size();
    int cnt, answer_index;
    for (int i = 0; i < len; i++) {
        cnt = 0;
        while (progresses[i] < 100) {
            progresses[i] += speeds[i];
            cnt++;
        }
        if (i == 0) {
            temp.push_back(cnt);
            answer.push_back(1);
            answer_index = 0;
        }
        else {
            if (cnt <= temp.back()) {
                answer[answer_index]++;
            }
            else {
                temp.push_back(cnt);
                answer.push_back(1);
                answer_index++;
            }
        }
    }

    //처음에 들어오는 건 무조건 넣는다
    //n번째 들어온 값이 stack에 있는 숫자보다 작으면 stack값 ++
    //n번째 들어온 값이 stack에 있는 숫자보다 크다면 stack+1값 ++

    return answer;
}