[스택/큐] 기능개발

yyeahh·2020년 8월 1일
0

프로그래머스

목록 보기
2/35

|| 문제설명 ||

  1. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있다.

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

  3. 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하라.

    - progresses : 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열
    - speeds : 각 작업의 개발 속도가 적힌 정수 배열
_작업의 개수(progresses, speeds배열의 길이) <= 100
_작업 진도 < 100, 자연수
_작업 속도 <= 100, 자연수
_배포는 하루에 한 번만 하루의 끝에 이루어진다

|| 코드 ||

[2020.07.28] 성공
#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;
}


[2020.07.29]
- 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;
}


[2021.01.15]
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;
}

0개의 댓글