[코딩테스트] [프로그래머스] 기능개발

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42586

---

풀이

1. 선입선출 구조의 큐를 사용해서 각 기능마다 완성까지 남은 날짜를 push한다.

2. 큐의 front를 최소 날짜로 잡고, 반환할 벡터(answer)에 1을 넣어준 뒤 pop한다.
   2-1. 큐의 top이 최소 날짜보다 크다면, 최소 날짜를 top으로 변경하고, 반환할 벡터에 1을 넣어준 뒤 pop한다.
   2-2. 아니라면, 우선순위가 후순위기 때문에 현재 최소 날짜에 배포된다. 따라서 answer의 마지막 원소에 1을 증가시키고, pop한다.

---

코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds)
{
    queue<int> days;
    
    for (int i=0; i<progresses.size(); i++)
    {
        int day = 0;
        int diff = 100 - progresses[i];
        while (diff > speeds[i] * day)
        {
            day++;
        }
        
        days.push(day);
    }
    
    vector<int> answer;
    
    int minDay = days.front();
    answer.push_back(1);
    days.pop();
    
    while(!days.empty())
    {
        if (minDay < days.front())
        {
            minDay = days.front();
            answer.push_back(1);
            days.pop();
        }
        else
        {
            answer[answer.size() - 1]++;
            days.pop();
        }
    }
    
    return answer;
}

---

다른 풀이와 코드

0. 나눗셈 올림(나머지가 있다면, 무조건 올린다)을 사용해서 최적화한 코드이다.

1. $\lceil \frac{A}{B} \rceil = \frac{A + B - 1}{B}$ (나눗셈 올림) 을 사용하여 각 기능마다 필요한 날짜 수를 구한다.

2. 반환할 벡터(answer)가 비어있거나, 필요한 날짜 수가 이전 기능 개발에 필요한 날짜 수보다 크다면 => 이전 기능 배포 후에 배포할 수 있다는 뜻이기에 answer에 1을 넣어준다.

3. 아니라면, 이전 기능에 필요한 날짜 수보다 작거나 같다는 뜻이기에 answer의 back을 증가시킨다.

4. 최대 날짜보다 현재 날짜가 더 클 경우, 최대 날짜를 갱신한다.

#include <string>
#include <vector>
using namespace std;

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

    int day;
    int max_day = 0;
    for (int i = 0; i < progresses.size(); ++i)
    {
        day = (99 - progresses[i]) / speeds[i] + 1;

        if (answer.empty() || max_day < day)
            answer.push_back(1);
        else
            ++answer.back();

        if (max_day < day)
            max_day = day;
    }

    return answer;
}

+) cmath 헤더를 추가하여 ceil 함수로 나눗셈 올림을 할 수 있다.

#include <string>
#include <vector>
#include <cmath>
using namespace std;

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

    int day;
    int max_day = 0;
    for (int i = 0; i < progresses.size(); ++i)
    {
    	int remain = 100 - progresses[i];
        day = static_cast<int>(ceil(remain / (double)speeds[i]));

        if (answer.empty() || max_day < day)
            answer.push_back(1);
        else
            ++answer.back();

        if (max_day < day)
            max_day = day;
    }

    return answer;
}