[프로그래머스 코딩테스트 고득점 Kit - 스택/큐] 기능개발

구현 문제

programmers.co.kr/learn/courses/30/lessons/42586

 

---

[문제 풀이]

 

동시에 배포되는 기능의 개수를 순서대로 묻는 문제입니다.

뒷 순서의 기능이 먼저 배포되어도 이전 단계가 배포되지 않는다면 기다렸다가 한 번에 배포합니다.

 

즉 배포되지 않은 가장 앞 순서의 기능보다 뒷 순서가 더 짧은 시간이 걸린다면 그들을 그룹으로 묶고, 더 오래 걸리는 기능이 뒷 순서에 등장한다면 묶은 그룹의 크기를 answer에 넣고 그룹의 기능들이 배포되었다고 확정하면 됩니다.

그렇다는 것은 그룹을 구성할지 새로운 그룹을 만들지는 현재 순서의 기능과, 그룹의 가장 첫 번째 기능의 시간만 계속 비교해주면 됩니다.

 

그래서 큐를 사용합니다.

큐는 그룹의 역할을 합니다.

 

가장 첫 번째, 가장 먼저 확인한, 먼저 들어간 것이 가장 앞에 오는 큐를 사용해야 하는 이유가 이것입니다.

기능별로 걸리는 시간을 기록하고, 가장 첫 번째 기능부터 큐에 넣습니다.

다음 기능을 전부 체크하면서 뒷 순서의 기능 개발이 더 짧다면 계속 큐에 넣습니다.

 

그러다가 더 오래 걸리는 시간이 온다면 answer에 큐의 크기를 넣고 큐를 비워버립니다.

그리고 다시 큐의 첫 번째 원소로 현재 걸리는 시간을 넣고 위의 과정을 반복합니다.

 

이제 주어진 두 배열로 걸리는 시간만 구해주면 풀이가 가능합니다.

100퍼센트가 채워지면 배포가 가능하므로 (100 - (현재 진행 단계)) / (개발 속도)를 올림한 값이 걸리는 시간과 같다는 것을 알 수 있습니다.

올림 값을 구하는 함수를 써도 좋고, 나머지가 0인 경우에 1을 더해도 좋습니다.

 

위처럼 $O(N)$의 시간 복잡도로 문제를 해결할 수 있습니다.

 

 

큐/스택 문제지만 큐가 필요가 없는 문제입니다.

기준을 먼저 큐에 넣고 기준과 비교를 시키는 문제이므로 큐를 사용하는 문제로 분류하였지만 큐가 없이 반복문을 써서도 풀 수 있습니다.

 

큐의 중간 원소를 쓰지 않고 전부 버리기 때문에 큐의 가장 앞쪽 원소를 따로 저장할 변수와

큐의 크기처럼 동시 배포하는 그룹의 크기를 저장할 변수 두 개면 큐 없이도 풀이가 가능합니다.

실제로 그 편이 메모리에도 이득입니다.

 

---

[소스 코드] / C++

 

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    queue<int> q;
    
    int N = progresses.size();
    for (int i = 0; i < N; i++) {
        int cur = (100 - progresses[i]) / speeds[i];
        if ((100 - progresses[i]) % speeds[i] != 0) cur++;
        
        if (q.empty()) q.push(cur);
        else {
            int pre = q.front();
            if (pre < cur) {
                answer.push_back(q.size());
                while (!q.empty()) q.pop();
            }
            q.push(cur);
        }
    }
    
    answer.push_back(q.size());
    
    return answer;
}

 

---

[메모]

 

• c++에서 반올림, 올림을 사용하려면 cmath헤더를 불러와야 한다.
• 반올림, 올림은 round, ceil