[Algorithm] 프로그래머스 : 기능개발

안녕하세요, 루피입니다.

오늘은 프로그래머스 기능개발 풀이를 기록하려합니다.

 

바로 시작합니다.

---

문제 분석

먼저 문제의 요구사항을 명확히 해야 합니다.

1. 각 기능은 100%가 되어야 배포 가능합니다.
2. 각 기능의 개발 속도는 모두 다릅니다.
3. 핵심 규칙: 뒤에 있는 기능이 먼저 개발되더라도, 앞에 있는 기능이 배포될 때 함께 배포됩니다.

예를 들어, 1번 기능이 7일 걸리고 2번 기능이 3일 걸린다면, 2번 기능은 3일 만에 완성되지만 1번 기능이 배포되는 7일 차에 함께 배포됩니다. 즉, 우리는 배포 그룹의 크기를 구해야 합니다.

---

풀이 전략

이 문제의 핵심은 "먼저 들어온 기능이 먼저 배포되어야 한다"는 점입니다. 이 규칙은 자료구조 큐(Queue)의 FIFO(First-In, First-Out) 특성과 정확히 일치합니다.

전략은 다음과 같습니다.

1. 각 기능이 배포되기까지 며칠이 걸리는지 계산합니다.
2. 이 '필요한 날짜'를 큐에 순서대로 넣습니다.
3. 큐의 맨 앞(front)에 있는 기능의 배포일보다 더 오래 걸리는 기능이 나타나면, 그때까지 큐에 쌓인 기능들을 한 그룹으로 묶어 배포합니다.

이 전략을 코드로 구현해 보겠습니다.

#include <string>
#include <vector>
#include <cmath> // ceil 함수 사용을 위해
#include <queue>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    queue<int> q; // 배포에 필요한 날짜를 저장할 큐

    for (int i = 0; i < progresses.size(); i++) {
        // 1. 각 기능의 배포 소요일 계산 (올림 처리)
        int day = ceil((double)(100 - progresses[i]) / speeds[i]);

        // 2. 배포 시점 확인
        // 큐가 비어있지 않고, 현재 기능이 앞선 기능보다 오래 걸린다면
        if (!q.empty() && q.front() < day) {
            // 그때까지 큐에 쌓인 기능들을 한 번에 배포
            answer.push_back(q.size());
            // 배포했으니 큐를 비움
            while(!q.empty()) q.pop();
        }

        // 3. 현재 기능의 소요일을 큐에 추가
        q.push(day);
    }

    // 4. 마지막에 큐에 남아있는 기능들을 배포
    answer.push_back(q.size());

    return answer;
}

---

코드 해설

1. 배포 소요일 계산

int day = ceil((double)(100 - progresses[i]) / speeds[i]);

• 100 - progresses[i]는 남은 작업량을 의미합니다.
• 이것을 속도 speeds[i]로 나누면 필요한 날짜가 나옵니다.
• 7% 남은 작업을 하루에 3%씩 하면 2.33..일이 걸리는데, 실제로는 3일이 필요합니다. 이렇게 소수점이 발생하면 무조건 올림 해야 하므로 ceil 함수를 사용합니다.
• ceil 함수는 double 타입에 동작하므로, 계산 과정에서 형변환을 해주는 것이 안전합니다.
  • 팁: <cmath> 헤더 없이 (남은작업량 + 속도 - 1) / 속도 공식을 이용하면 정수 연산만으로도 동일한 올림 결과를 얻을 수 있습니다.

2. 배포 그룹 결정 

if (!q.empty() && q.front() < day) {
    answer.push_back(q.size());
    while(!q.empty()) q.pop();
}

• q.front()는 현재 배포를 기다리는 그룹에서 가장 오래 걸리는 기준 배포일을 의미합니다.
• 새로 들어온 기능의 소요일 day가 이 기준일(q.front())보다 크다는 것은, 더 이상 같은 날에 배포될 수 없다는 의미입니다.
• 따라서 이 시점에, 지금까지 큐에 쌓여있던 기능들(q.size()개)을 하나의 그룹으로 묶어 answer에 추가하고 큐를 비워 새로운 배포 그룹을 준비합니다.

3. 마지막 그룹 처리

answer.push_back(q.size());

• for문이 모두 끝난 후에도 큐에는 마지막 배포 그룹이 남아있습니다. 이들을 잊지 말고 answer에 추가해줘야 합니다.

---

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

프로그래머스

오늘도 화이팅입니다!