처음에 '스택과 큐 모두 이용해서 풀어지겠다'라는 생각에 시간이 조금 걸렸다. 오랜만에 lv02문제를 풀어서 그런지.. 1시간 정도 걸린 것 같다.
앞 쪽의 작업이 끝나기 전에는 뒤 쪽작업들을 맨 앞의 작업보다 더 오래 걸리는 작업이 생기기 전까지 모두 대기 큐에 넣어서, 대기 큐에 있는 작업들을 처리하고, 또 다음 작업들을 처리하는 방식으로 문제를 해결하려고 했다.
그런데 문제를 잘 이해해보면 문제에서는 각 작업들이 '언제' 끝났는지는 알 필요가 없기 때문에, 대기 큐에 넣지 않고 그냥 카운팅만 하여서 문제가 해결될 것 같았다.
자세한 풀이는 코드를 보며 하겠다.
문제 풀이
소스코드 : C++
#include <iostream>
#include <vector>
using namespace std;
vector<int> solution(vector<int> progresses, vector<int> speeds) {
vector<int> answer;
int max_day = 0;
for (int i = 0; i < progresses.size(); ++i){
int day = (99 - progresses[i]) / speeds[i] + 1;
if (answer.empty() || max_day < day) {
answer.push_back(1);
max_day = day;
}
else answer.back()++;
}
return answer;
}
대기 큐 : 이전의 작업이 완료되기까지 다음의 작업들이 대기하는 큐
작업을 처리하는데 걸리는 시간 day = (99 - progresses[i]) / speeds[i] + 1으로 구해준다.
여기서 100 - progresses[i]가 아니라 99 - progresses[i]인 이유는 어짜피 작업을 완료하려면 100이상이 되어야 하기 때문에 99로 계산하여 +1을 해준 것이다. answer가 스택과 대기큐 두 가지 역할 둘 다 하는 것이다.
answer가 비어있을 때는 작업 처리가 시작되었으므로 하나의 작업을 push해주고 그 다음 작업이 먼저 끝난다면 대기 큐에 넣는 의미인 answer.back()++를 해준다.
각 작업들이 이전 작업보다 짧게 걸린다면 대기 큐에 들어가야하는 작업들이므로 현재 이루어지고 있는 작업의 개수를 의미하는 answer의 top에 있는 원소를 1씩 증가시켜준다.
다음 작업이 만약 이전 작업들 중 가장 오래 걸리는 작업보다 큰 작업이 나온다면, 그 때부터 새로운 작업이 시작되므로 if (answer.empty() || max_day < day) 여기서 max_day = day 처리해주고 answer.push_back(1)을 하여 새로운 대기 큐로 넘어간다.
소스코드 : Python
파이썬 풀이 역시 로직자체는 같다. for 문을 range(len(...))을 이용하기보단 zip으로 묶어서 한 번에 처리하는게 더 좋을것 같아서 zip을 이용하여 풀었다.
def solution(progresses, speeds):
answer = []
max_day = 0
for p, s in zip(progresses, speeds):
day = (99 - p)//s +1
if len(answer) == 0 or max_day< day:
max_day = day
answer.append(1)
else: answer[-1]+=1
return answer
