기능개발

기능개발의 문제는 큐의 개념을 이용한 문제였다.

큐의 선입선출의 개념을 이용하였다.

🌼 문제

현재 n의 값은 100이기 때문에 $O(n^3)$ 시간복잡도 내에서 문제를 해결 할 수 있다.

(progresses, speeds배열을 큐라고 쓰겟다)
이 문제의 경우 progresses큐의 첫번째 요소가 끝나는 시간을 찾는다. 찾는 방법은 100에서 progresses의 첫번째 요소 값을 뺀 결과를 speed큐의 첫번째 요소로 나누면 된다. 여기서 주의할 점은 나눈 값은 올림처리를 해야한다. 그리고 progresses, speed의 첫번째 요소를 pop한다. 그리고 오나료가 된 작업을 나타내는 cnt 변수 값을 1로 설정한다.

그리고 반복문을 통해서 나머지 progresses 요소들을 돈다. 앞에서 작업을 종료시키는데에 걸린시간*speeds를 progresses의 첫번째 요소에 더하여 그 값이 100보다 크거나 같은지를 확인을 한다. 만약에 그렇다면 cnt값을 +1 해주고, 큐의 값을 앞과 같이 pop 한다.

그 이후 반복문이 종료되면, int형을 저장하는 임의의 벡터에 cnt값을 저장하고 cnt 값을 1로 초기화한다. 그 이유는 큐안에 값들이 존재 할 때 다시 작업이 끝나는 시간을 구하고 계산을 하기 위해서이다.

🌼 풀이

#include <iostream>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    int cnt = 1;
    vector<int> res;
    float date = 0.0f;
    
    while(progresses.empty() == 0)
    {
        float need = 100-progresses[0];
        date += need/speeds[0];
        date = ceil(date);
        
        progresses.erase(progresses.begin());
        speeds.erase(speeds.begin());
        
        int i = 0;
        
        while(i < progresses.size())
        {
            progresses[i] += date*speeds[i];
            if(progresses[i] >= 100)
            {
                cnt++;
                progresses.erase(progresses.begin());
                speeds.erase(speeds.begin());
            }
            else break;
        }
        res.push_back(cnt);
        cnt = 1;
    }
    
    return res;
}

🌼 C++ Queue

큐헤더파일
#include <queue>

큐선언
queue<int> q;

큐 데이터추가
queue.push(element)

큐 데이터삭제
queue.pop()

큐의 첫번째요소
queue.front()

큐의 마지막요소
queue.back()

큐 사이즈반환
queue.size()

큐가 비었는지 확인
queue.empty()

두 큐의 내용을 변경
swap(queue1 , queue2)