[프로그래머스] 기능개발 (Lv.2)

---

문제 링크

---

프로그래머스 - 기능개발

문제 설명

---

기능마다 현재 진도율 progresses와 하루 작업량 speeds가 주어진다. 배포는 앞 기능이 완료되어야 뒷 기능도 함께 배포할 수 있다. 각 배포마다 몇 개의 기능이 배포되는지 배열로 반환하라.

예) progresses = [93, 30, 55], speeds = [1, 30, 5]

• 1번 기능: (100 - 93) / 1 = 7일 후 완료
• 2번 기능: (100 - 30) / 30 = 3일 후 완료 → 1번 기다려야 하므로 7일째 함께 배포
• 3번 기능: (100 - 55) / 5 = 9일 후 완료 → 단독 배포 → [2, 1]

내 풀이

---

front 인덱스로 아직 배포되지 않은 첫 번째 기능의 위치를 추적한다. 매일 front부터 끝까지 speed를 더한 뒤, front 기능이 100 이상이 되면 연속으로 100 이상인 기능들을 카운트해서 한 번에 배포한다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    int front = 0;
    int n = progresses.size();
    
    while(front < n)
    {
        for(int i = front; i < n; i++)
        {
            progresses[i] += speeds[i];
        }
        
        if(progresses[front] >= 100)
        {
            int count = 0;
            while(front < n && progresses[front] >= 100)
            {
                front++;
                count++;
            }
            
            answer.push_back(count);
        }
    }
    
    return answer;
}

시간복잡도 분석

---

| 연산 | 복잡도 | 이유 | |——|——–|——| | 하루 진행 (for loop) | O(n) | front부터 끝까지 speed 더하기 | | 배포 처리 (while) | O(n) | 전체 합산 최대 n번 | | 전체 | O(d × n) | d = 최대 진행 일수 |

progresses 최솟값 1, speeds 최솟값 1일 때 최대 99일, n ≤ 100이므로 O(99 × 100) = O(9,900) → 충분히 통과 가능하다.

오답노트

---

오답노트는 아니지만, 생각한 흐름도를 코드로 옮기는 데 시간이 오래 걸렸다.

후기

---

코테를 다시 풀기 시작한 지 얼마 되지 않은데다가, 다시 풀기 시작한 이후로 레벨 2는 처음 시도하는 거라서 그런지 머릿속에 있는 흐름도를 코드로 구현해내는데 시간이 오래 걸렸다.
익숙해질 수 있도록 꾸준히 풀어야겠다.

• algorithm
• codingtest
• stack
• queue