프로그래머스 Lv2 스택/큐 기능개발

https://school.programmers.co.kr/learn/courses/30/lessons/42586

프로그래머스

나는 큐와 우선순위 큐를 사용해서 정답을 내려고 했다.

큐를 순회하며 데이터를 늘리고, 우선순위 큐를 인덱스로 정렬 해 top()이 100이상이라면 우선순위 큐를 순회하며 

하루에 릴리즈되는 기능을 셀려고했다.

 

하지만 다른 사람 풀이를 보니, 시작 인덱스를 설정하고 이게 progresses보다 작다면 반복문을 돌리도록 했다.

 

내 코드에서는 큐를 순회하는 순간을 어떻게 끝낼까가 문제였는데, 이 부분은 벡터를 사용하여 끝내는 것이 맞았다.

그리고 벡터 내에서 우선순위 큐를 사용해서 답을 구하면 문제가 풀릴 것 처럼 보였다.

 

다른 사람 풀이는 아래의 과정과 같다.

시작 인덱스가 progresses보다 작은 조건으로 반복문을 순회한다.

 

제일 앞에 값이 100 이상이라면 시작부터 마지막까지 progresses를 큐안에 담고

반복문을 돌리며, 큐의 front()가 100이상이라면 하루에 릴리즈되는 숫자를 증가시켰다.

만약 front()가 100미만이라면 시작인덱스에 하루에 릴리즈 되는 수를 더 해주고, 정답 벡터에 릴리즈 숫자를 추가했다.

 

제일 앞에 값이 100 미만이라면

시작부터 마지막까지 progresses에 speeds 값을 더해준다.

 

생각해보니,,,우선순위 큐를 쓰는건 효율적이지 않은 것 같다. 

 

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

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) 
{
   vector<int> answer;
    int start = 0;
    
    while(start < progresses.size())
    {
        if(progresses[start] >= 100)
        {
            queue<int> q;
            
            for(int i = start; i < progresses.size(); ++i)
                q.push(progresses[i]);
            
            int count = 0;
            
            while(1)
            {
                if(!q.empty() && q.front() >= 100)
                {
                    ++count;
                    q.pop();
                }
                else
                {
                    answer.push_back(count);
                    start += count;
                    break;
                }
            }
        }
        else
        {   
            for(int i = start; i < progresses.size(); ++i)
                progresses[i] += speeds[i];
        }
    }
    

    return answer;
}