프로그래머스_코딩테스트연습_스택/큐_기능개발

♠ 소스코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <iterator>
using namespace std;

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

    vector<int> answer;

    int size = progresses.size();
    //cout <<size <<endl; // for debug
    queue<int> my_progresses;

     for(int i=0; i<size; i++)
    {
        int progress_left = 100 - progresses[i];
        int days_left = progress_left / speeds[i]; 
        if( progress_left % speeds[i] ) days_left ++;

          my_progresses.push( days_left );

    }
    
    // 첫 배포
    int done = my_progresses.front();
    my_progresses.pop(); //배포 실행

    int cnt = 1;

     if(my_progresses.empty()) { answer.push_back(cnt); }
    // 배포 진행
    while( !my_progresses.empty() )
    {
        if( my_progresses.front() > done )

          {

                answer.push_back(cnt);

                cnt = 1;

                done = my_progresses.front();

          }

         else { cnt++; }
        //cout << "done " << done << "   cnt " << cnt << endl; //for debug
        my_progresses.pop(); //배포 실행
        if(my_progresses.empty())  { answer.push_back(cnt); }
    }
    return answer;
}

 

♠ 고찰

▶ 문제 이해

가장 앞에 있는 작업 진도가 100%일 때 / 뒤에 이미 진행이 완료된 작업이 있다면 함께 배포되는 문제이다.

함께 배포될 때, 작업들은 연속되어야 하고, 그 사이에 진행이 완료되지 않은 작업이 있다면 함께 배포될 수 없다.

ex. progesses = [1  2  1], speeds = [1 1 1]일 때 answer = [1 2]가 된다.

 

▶ 알고리즘은,

1) 각 작업의 남은 일수를 계산하여 큐 my_progresses에 넣고,

2) 첫 배포 실행

 - done변수에 현재 배포까지 작업일수를 저장한다.

3) while문 : loop를 한 번 돌 때 한 작업씩 배포한다.

 - 만약 my_progresses의 front의 값(남은 일수)이 현재까지 작업일수보다 크다면 새로 배포해야 한다. 따라서 cnt를 answer에 넣고, cnt는 1로 초기화, done도 현재 작업일수로 set한다.

 - 만약 my_progresses의 front의 값(남은 일수)이 현재까지 작업일수보다 작다면 이전 배포와 함께 배포될 수 있다. 따라서 cnt +1한다.

 

▶ 실수한 부분

처음 코드를 작성했을 때 하나의 테스트케이스(#11)를 실패했었다.

첫 코드에서는 남은 일수를 계산할 때 cmath의 ceil()함수를 사용했었다.

다른 사람의 후기를 보니 math의 ceil()함수때문이라고 하여 이 부분을 수정하였다.

ceil()함수 리턴값이 double형이라고 해서 int형 변수 선언해서 값을 받아 넣기도 하고(자동형변환), 강제형변환을 통해 넣어보기도 했는데, 계속 실패한다. 

아직은 그 이유를 모르겠다.