[프로그래머스] 기능 개발 42586 (Level 2) - C++

문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/42586

---

📌 문제 요약

각 기능은 순서대로 개발되며, 다음과 같은 규칙을 가진다.

• 기능마다 현재 진행률(progresses)과 하루 개발 속도(speeds)가 주어진다.
• 기능은 앞에 있는 기능이 완료되어야만 배포 가능하다.
• 하루가 지날 때마다 모든 기능의 진행률이 증가한다.
• 배포 시에는 연속된 기능들만 함께 배포된다.

---

입출력 예

progres	speed	return
[93, 30, 55]	[1, 30, 5]	[2, 1]
[95, 90, 99, 99, 80, 99]	[1, 1, 1, 1, 1, 1]	[1, 3, 2]

---

💭 처음 접근: “요세푸스 문제처럼 순번을 계속 넘겨야 하네?”

문제를 처음 봤을 때 떠올린 생각은 이랬다.

• 작업들이 순서대로 줄을 서 있음
• 앞 작업이 끝나야 뒤 작업도 나갈 수 있음
• 매일 모든 작업의 진행률이 증가함

👉 순서를 유지하면서 계속 순환해야 하므로
👉 자연스럽게 Queue가 떠올랐다.

그래서 “하루하루 진행시키는 시뮬레이션” 방식으로 풀었다.

---

첫 번째 풀이 (시뮬레이션 기반)

#include <string>
#include <vector>
#include <queue> //왜 꼭 queue여야 하는지 생각
using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    queue<int> q;
    queue<int> s;
    //progresses가 줄어들면 speeds도 줄어듦 -> 반복횟수 매번 다름
    // 한 번의 순회는 speeds의 개수만큼
    vector<int> answer;
    for(int i=0;i<progresses.size();i++){
        q.push(progresses[i]);
        s.push(speeds[i]);
    }
    int num;
    while(!q.empty()){
        num=0;
        int l=s.size();
        for(int j=0;j<l;j++){
            int spe= s.front();
            int tmp=q.front()+=spe;
            q.pop();
            s.pop();
            q.push(tmp);
            s.push(spe);
        }
        for(int j=0;j<l;j++){
        int t= q.front();
        if(t>=100){
            q.pop();
            s.pop();
            num++;
        }
        }
        if(num == 0) continue;
        answer.push_back(num);        
    }
    return answer;
}

👉 결과는 맞았지만, 솔직히 말해 “살짝 때려맞춘 느낌”이 강했다.

---

왜 이 문제가 큐(Queue) 문제인가?

1.  FIFO가 반드시 보장되어야 한다

문제의 핵심 조건:

뒤에 있는 기능이 먼저 완성돼도,
앞에 있는 기능이 배포될 때 함께 배포된다

 

즉,

• 순서가 절대 뒤바뀌면 안 됨
• 항상 맨 앞(front)만 확인하면 됨

👉 FIFO(First-In First-Out) 구조가 정확히 맞아떨어진다.

---

2. 선두(Front)의 상태가 전체를 결정한다

• 앞 기능이 100%가 아니면 → 아무도 배포 불가
• 앞 기능이 100%가 되면 → 뒤에서 연속으로 가능한 만큼 배포

👉 우리는 항상 front만 관찰하면 된다.

---

3. 자료구조 선택 마인드셋

코테에서 자료구조를 고를 때 스스로에게 던지는 질문:

1. 먼저 들어온 게 먼저 나가야 하나? → Queue
2. 최근 것이 중요하나? → Stack
3. 중간 삽입/삭제가 많나? → Linked List
4. 빠른 조회가 중요한가? → Hash(Map/Set)

👉 이 문제는

“작업들이 줄 서 있고, 앞사람이 안 나가면 뒷사람도 못 나간다”
→ Queue가 정답

---

현재 풀이의 한계

현재 풀이는 “하루하루 시뮬레이션” 방식이다.

• 작업이 1% 남고 속도가 1이면 → 99번 반복
• 최악의 경우 불필요한 반복이 많아짐

👉 시간 복잡도는 불필요하게 커진다

---

사고 전환: 시뮬레이션 → 수학적 모델링

핵심 아이디어

“굳이 하루씩 진행할 필요가 있을까?”
“각 기능이 며칠 뒤에 끝나는지만 알면 되지 않을까?”

---

최적화 포인트 1: 남은 일수 계산

• 남은 작업량: 100 - progresses[i]
• 하루 작업량: speeds[i]
• 필요한 일수 (올림 처리):

 

(99 - progresses[i]) / speeds[i] + 1

---

최적화 포인트 2: 완료일 기준 묶기

• 앞 기능의 완료일을 기준으로
• 그보다 빨리 끝나는 기능은 함께 배포

---

개선된 풀이 (O(N))

 

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

    // 1. 모든 기능의 '필요 일수'를 미리 계산해서 큐에 넣기
    for (int i = 0; i < progresses.size(); i++) {
        int day = (99 - progresses[i]) / speeds[i] + 1;
        days.push(day);
    }

    // 2. 큐가 빌 때까지 배포 묶음 계산
    while (!days.empty()) {
        int current_deploy_day = days.front(); // 기준이 되는 앞선 기능의 완성일
        days.pop();
        int count = 1;

        // 기준일보다 빨리 끝나는 뒤의 기능들을 한꺼번에 pop
        while (!days.empty() && days.front() <= current_deploy_day) {
            days.pop();
            count++;
        }
        answer.push_back(count);
    }
    return answer;
}

---

이 문제에서 배운 점

1. 시뮬레이션 vs 수학적 접근
   • 시뮬레이션은 직관적이지만 느릴 수 있음
   • 결과값(완료일)을 미리 계산하면 훨씬 효율적
2. 큐는 단순한 저장소가 아니다
   • 기준(front)을 잡고
   • 그 기준과 비교하며 흐름을 제어하는 도구
3. “왜 이 자료구조인가?”를 설명할 수 있어야 한다
   → 이 문제가 좋은 연습 문제인 이유

---

📂 개인 문제풀이 레포

https://github.com/zzmnxn/algorithm-study