[Algorithm] 프로그래머스 기능개발 - C++

코딩테스트 연습 - 기능개발

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

const int MAX = 100;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    queue<int> q;
    // make input
    for(int i = 0; i < progresses.size(); i++){
        int developSpeed = speeds[i];
        int leftDevelop = MAX - progresses[i];
        int days = leftDevelop / developSpeed;
        if(leftDevelop % developSpeed > 0)  days++;

        q.push(days);
    }

    // sort
    while (!q.empty()){
        int curLeftDays = q.front();    q.pop();
        int developed = 1;

        while ((!q.empty()) && q.front() <= curLeftDays){
            q.pop();
            developed++;
        }
        answer.push_back(developed);
    }

    return answer;
}

---

 처음에는 위상정렬인줄 알았으나 '한번에 개발될 수 있는 항목이 몇개' 인지를 구하는 문제였습니다. 그래서 위상정렬보다 간단하게 2가지 로직만 지나면 해결할 수 있었습니다.

 

- 개발이 남은 시간 / 한번 하는데 걸리는 개발 시간 (나머지 있을시 +1)을 해서 개발까지 걸리는 총 날짜를 구합니다.

- 이후 큐에서 하나씩 보면서 이후 기능의 개발이 현재 개발보다 빠르다면 '개발 가능수+1' 을 해서 정답에 넣어주면 됩니다.

 

 말이 어려워서 그렇지 코드를 보면 이해가 더 잘 되실거라고 봅니다.