각 기능은 진도가 100%일 때 서비스에 반영할 수 있다.
각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포된다.
각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하라.
- progresses : 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열
- speeds : 각 작업의 개발 속도가 적힌 정수 배열
_작업의 개수(progresses, speeds배열의 길이) <= 100
_작업 진도 < 100, 자연수
_작업 속도 <= 100, 자연수
_배포는 하루에 한 번만 하루의 끝에 이루어진다
#include <string>
#include <vector>
using namespace std;
vector<int> solution(vector<int> progresses, vector<int> speeds) {
vector<int> answer;
int day[105];
for (int i=0; i<progresses.size(); i++) {
day[i] = (100 - progresses[i]) / speeds[i];
day[i] = (100 - progresses[i]) % speeds[i] ? day[i] + 1 : day[i];
}
int max = day[0], cnt = 1;
for (int i=1; i<progresses.size(); i++) {
if (max < day[i]) {
answer.push_back(cnt);
cnt = 1;
max = day[i];
}
else {
cnt++;
}
}
answer.push_back(cnt);
return answer;
}
- for문 하나만 쓰기
#include <string>
#include <vector>
using namespace std;
vector<int> solution(vector<int> progresses, vector<int> speeds) {
vector<int> answer;
int day, max = 0, cnt = 0;
for (int i = 0; i < progresses.size(); i++) {
day = (99 - progresses[i]) / speeds[i] + 1;
if (!i) {
max = day;
}
if (max >= day) { cnt++; }
else {
answer.push_back(cnt);
cnt = 1;
max = day;
}
}
answer.push_back(cnt);
return answer;
}
1) O(n) : 100*n으로 최악의 경우 약 10000
최대 100일이 걸리므로 for문으로 100만큼 돌리고 그 안에 n만큼의 포문을 돌려 날짜별로 돌리는 방법
2) O(n) : n으로 최악이더라도 약 100
for문으로 n번을 돌면서 그날 작업이 얼마나 걸리는지를 기준으로 함.
progresses[i]가 전 작업보다 많냐 적냐를 이용
#include <string>
#include <vector>
using namespace std;
vector<int> solution(vector<int> progresses, vector<int> speeds) {
vector<int> answer;
int top = 0, cnt = 0, progress;
for(int i=0; i<progresses.size(); i++) {
progress = (99 - progresses[i]) / speeds[i] + 1;
if(progress > top) {
if(top) answer.push_back(cnt);
top = progress;
cnt = 1;
}
else cnt++;
}
answer.push_back(cnt);
return answer;
}