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

문제

[기능 개선 작업] 각 기능 목표 : 100%
- 개발 속도 모두 다름
- 뒤에 기능은 앞이 완료돼야 배포됨

정수 배열
배포 순서 : progresses with 작업 진도
개발 속도 : speeds

작업 수 <= 100
작업 진도 < 100 자연수
작업 속도 <= 100
배포 : 하루에 한 번, 하루의 끝

@ 각 배포마다 몇 개의 기능이 같이 배포되는지

 

[문제 이해]

progresses	speeds		return
93, 30, 55	1, 30, 5	7일 걸림, 3일 걸림, 9일 걸림	2, 1
95, 90, 99, 99, 80, 99	1, 1, 1, 1, 1	5, 10, 1, 1, 20, 1일 걸림	1, 3, 2

 

도출

각 기능이 얼마의 날을 요구하는지 계산 필요

앞에서부터 하나씩 고려하는 동안, 뒤에 기능이 완료될 수 있음을 감안해야 함 -> 총 경과일 변수 필요

 

[풀이 생각 / 반복문 과정]

큐 days
5, 10, 1, 1, 20, 1

첫 값이 경과일인 1일 보다 큼 => 오늘은 5일이 됨
while(오늘과 같으니) => k=1; 큐는 10, 1, 1, 20, 1되고 10은 5일보다 크니까 반복문 끝
k가 1이니 answer에 1추가

첫 값이 10이니 오늘 5일 보다 큼 => 오늘은 10일이 됨
while(오늘과 같으니) => k=1; 큐는 1, 1, 20, 1되고 1은 10보다 작으니 k=2; 큐는 1, 20, 1되고 1은 10보다 작으니 k=3; 큐는 20, 1되고 반복문 끝
k=3이니 answer에 3추가

첫 값이 20이니 오늘 10일보다 큼 => 오늘은 20일이 됨
while(오늘과 같으니) => k=1; 큐는 1이 되고 1은 20보다 작으니 k=2; 

if days = 1, 1, 1, 1
첫 값이 경과일인 1일임 => 오늘 1일 유지
while(오늘과 같으니) cnt=1; 큐는 1, 1, 1되고 cnt=2; 큐는 1, 1되고 cnt=3; 큐는 1되고 cnt=4 큐는 없음 반복문 끝
cnt=4이니 answer에 4추가 끝

 

if days = 2, 0, 0, 3

 

 

* 주의할 점
ceil함수 코드에서 int끼리 나누면 소수점이 없는 int -> float 혹은 double로 나누기

큐에서 마지막 남은 것까지 pop()으로 꺼낸 후에 while문의 front() 검사하지 않도록 -> !큐.empty() 조건 추가

 

#include <string>
#include <vector>
#include <cmath>
#include <queue>

using namespace std;

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

    for (int i = 0; i < progresses.size(); i++) {        
        days.push(ceil((100 - progresses[i]) / (float) speeds[i]));
    }

    int today = 1;
    while (!days.empty()) {
        int cnt = 0;

        if (days.front() > 0)
            today = days.front();

        while (!days.empty() && days.front() <= today) {
            cnt++;
            days.pop();
        }

        if (cnt > 0) 
            answer.push_back(cnt);
    }

    return answer;
}

 

너무 반복문이 많아서 줄일 수 없을까 고민 -> 완료!

 

다른 풀이 방법

#include <string>
#include <vector>
#include <cmath>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    
    int today = 1;

    for (int i = 0; i < progresses.size(); i++) {
        int need = ceil((100 - progresses[i]) / (float)speeds[i]);

        if (answer.empty() || need > today)
            answer.push_back(1);
        else
            answer.back()++;
        
         if (today < need)
            today = need;
    }
    return answer;
}

 

 

스택 / 큐 로 들어간 거라 무조건 스택 / 큐가 효율적이라는 생각에 사로잡혀서 헤맨..