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

문제요약

1. 우선순위 순으로 정렬돼 있으며 일들의 현재의 진척도를 담은 progresses배열이 주어집니다.
2. progresses 배열과 사이즈가 같으며 각 일을 하루에 올릴 수 있는 진척도를 담은 speeds 배열이 주어집니다.
3. 배포 규칙
   진척도 100퍼센트 달성한 일들만 배포가 가능합니다.
   우선순위가 높은 일보다 낮은 일이 먼저 배포돼서는 안되지만 어떤 일을 배포할 때 우선 순위가 낮은 일이 이미 100퍼센트를 달성했다면 함께 배포해도 됩니다.

아이디어

큐를 사용한 시뮬레이션을 해주면 된다.
끝나는 날들에 대한 큐를 만들어주었다.

끝나는 날은 문제 설명대로
남은 진척도 = (100-현재진척도)
남은 날수 = (남은 진척도)/(이 일의 속도) + (나머지==0 ? 0 : 1)

하루마다 앞에서부터 빼주는데 스트로크로 끊기지 않고 같이 빼줄 수 있는 것들(맨 앞 끝나는 날 이하들)을 같이 빼준다.

3 3 3 6 3 과 같이 달성된다 하더라도
5번째 일이 앞 3개와 함께 3일째에 배포될 수 있는 건 아니다.
5번째 일은 4번째 일과 함께 6일째에 배포될 것이다.

!! 주의 !! 배포할 수 있는 기능이 없는 날엔 기록을 하지 않는다.

삽질(금방 해결했지만)

맨 앞거랑 동시에 끝나는 것들도 빼줘야하는데 부등호에 같다 표시를 빼먹었다.

코드 2트

5분컷

• queue를 쓸 필요 없이 벡터를 사용하며 ctr로써 큐의 front를 표현
• 0개의 배포가 이루어지는 날은 스킵하기!

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    //진도가 100퍼센트일 때 서비스에 반영
    int ctr = 0;
    
    while(ctr<progresses.size()){
        for(int i = ctr;i<speeds.size();i++){
            progresses[i]+=speeds[i];
        }
        //ctr컨트롤
        int cur_ctr = ctr;
        for(int i =ctr;i<speeds.size();i++){
            if(progresses[i]<100) break;
            ctr++;
        }
        if(ctr-cur_ctr!=0)
            answer.push_back(ctr-cur_ctr);
    }
    return answer;
}

코드

#include <string>
#include <vector>

using namespace std;
//그냥 vector 인덱스 옮겨가면서 해도..
vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    vector<int> l;//how long will it take?
    for(int i = 0;i<progresses.size();i++){
        if((100-progresses[i])%speeds[i]==0){
            l.push_back((100-progresses[i])/speeds[i]);
        }
        else{
            l.push_back((100-progresses[i])/speeds[i]+1);
        }
    }
    int j;
    for(int i =0;i<l.size();i = j){
        //i가 우선순위를 따라가는 거임 하루에 한번만 움직일 수 있음
        int cur = l[i];//i우선순위인 일의 걸리는 시간
        int ctr = 1;
        for(j =i+1;j<l.size();j++){
            if(l[j]<=cur){
                ctr++;
            }
            else{
                break;
            }
        }
        answer.push_back(ctr);
    }
    return answer;
}