[Programmers - lv02] 기능개발 (cpp / python)

기능개발

코딩테스트 연습 - 기능개발

문제 설명

처음에 '스택과 큐 모두 이용해서 풀어지겠다'라는 생각에 시간이 조금 걸렸다. 오랜만에 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