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

https://programmers.co.kr/learn/courses/30/lessons/42586?language=cpp 

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

문제 분석

input : 작업량, 작업 속도

output : 각 배포마다 몇 개의 기능이 배포되는가?

세부 조건 : 각 작업은 병렬로 처리되지만 앞에 있는 작업이 완료되지 않으면 배포될 수 없다.

=>stack의 top이 완료되지 않으면 이전에 완료된 작업이 배포되지 않다가 완료되면 배포한다.

기본적으로 모든 stack의 요소에 접근해야 하기 때문에 O(N)의 시간 복잡도를 갖는다.

N은 작업 배열의 크기이다.

 

n 번째 작업에 접근

if 지금까지 작업이 진행된 작업 일수 * 스피드+ 작업량이 100 이상인 경우 

=>k번째 일 수에 끝난 작업의 수 +1하고 루프의 첫번째로 돌아간다.

if (100 - 작업량)를 n번째 작업의 스피드로 나눈 나머지가 0일 경우

=>k = (100-작업량)/스피드

0이 아닌 경우

=>k = (100-작업량)/스피드+1

 

시간 복잡도 : O(n)

공간 복잡도 : O(n)

 

사용할 자료구조 : vector

https://www.geeksforgeeks.org/vector-in-cpp-stl/