문제

Programmers, 기능개발

핵심

• 입력의 크기가 $10^2$이라 시간복잡도 보다는 구현에 집중한다.
• 앞에 기능이 배포될 때 뒤의 기능도 함께 배포되므로, 큐 자료구조를 이용해 배포 순서를 관리한다. 큐의 상단 기능이 배포 완료 될 때까지 걸린 기간을 구하고, 그 기간만큼 뒤에 기능들에도 진행도를 더한다. 뒤에 기능들도 배포가 가능하다면 첫 번째 기능이 배포될 때 뒤에 기능들도 함께 배포하도록 한다.

개선

코드

시간복잡도

• $O(N)$

C++

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

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    queue<int> q;
    for (auto e : progresses) 
        q.push(e);
    int idx = 0;
    int day = 0;
    int pass = 0;
    while (!q.empty()) {
        auto cur = q.front();
        cur += day * speeds[idx];
        while (cur < 100) {
            if (pass != 0)
                answer.push_back(pass);
            cur += speeds[idx];
            ++day;
            pass = 0;
        }
        q.pop();
        ++idx;
        ++pass;
    }
    if (pass != 0)
        answer.push_back(pass);
    return answer;
}

Java

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        Queue<Integer> q = new ArrayDeque<>();
        ArrayList<Integer> a = new ArrayList<>();
        for (var e : progresses)
            q.add(e);
        int idx = 0;
        int day = 0;
        int pass = 0;
        while (!q.isEmpty()) {
            int cur = q.peek();
            cur += day * speeds[idx];
            while (cur < 100) {
                if (pass != 0)
                    a.add(pass);
                cur += speeds[idx];
                ++day;
                pass = 0;
            }
            q.remove();
            ++idx;
            ++pass;
        }
        if (pass != 0)
            a.add(pass);
        int[] answer = new int[a.size()];
        idx = 0;
        for (var e : a)
            answer[idx++] = e;
        return answer;
    }
}