https://programmers.co.kr/learn/courses/30/lessons/42586
생각을 짧게 하고 시도했다가 방법이 너무 산으로 갔던 문제..(문제를 끝까지 제대로 안읽음😠) 처음 주어진
progresses
,speeds
를 이용해 배포까지 걸리는 날짜를 계산해주는 것이 포인트다.
작업진도와 속도를 이용해 배포까지 걸리는 날짜
를 모두 계산하여 큐에 넣는다.
예를 들면 작업진도가 [93,30,55]
, 속도가 [1,30,5]
일 경우 큐에는
(front) [7, 3, 9]
(back) 이런 형태로 배포까지 걸리는 날짜가 들어갈 것이다.
이때, 현재 front
값을 pop
한 후, 순차적으로 큐의 front
에 더 큰 수가 나오기 전까지는 모두 한 번에 배포할 수 있는 기능이다. (배포까지 걸리는 날짜가 더 적은 것!) 따라서 더 큰수가 나오기 전까진 pop
하면서 개수를 세주고 answer벡터에 push해준다.
이 과정을 큐가 모두 빌 때까지 반복하면 된다.
#include <string>
#include <vector>
#include <queue>
using namespace std;
vector<int> solution(vector<int> progresses, vector<int> speeds) {
vector<int> answer;
//배포까지 걸리는 날짜!
queue<int> requiredDays;
for(int i=0;i<progresses.size();i++){
int days=(100-progresses[i])/speeds[i];
if((100-progresses[i])%speeds[i]!=0) days++;
requiredDays.push(days);
}
//배포까지 걸리는 날짜 기준으로, 한 번에 같이 배포될 수 덩어리들 찾기 (바로 앞 front의 날짜가 더 커야함)
while(!requiredDays.empty()){
int curDay=requiredDays.front();
requiredDays.pop();
int cnt=1;
while(curDay>=requiredDays.front()&&!requiredDays.empty()){
requiredDays.pop();
cnt++;
}
answer.push_back(cnt);
}
return answer;
}