[ 프로그래머스-lv2 / 스택 ] 기능개발

1. 문제

---

 

프로그래머스

 

 

2. 소스코드

---

1회차

 

- 왜 문제 분류가 Stack/Queue인지 잘모르겠다. 그래서 그냥 while문, for문 반복문으로 vector를 순회함.

 

- 예상 시간 복잡도

(1) while 문 : 최악의 경우 맨 앞의 작업이 0에서 +1씩, 총 100회

(2 - 1) speed 더하기 : O(N)

(2 - 2) 조건 충족 확인 : O(N)

 

(1) x ( (2-1) + (2-2) ) = O(N)

 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prog, vector<int> speeds) {
    vector<int> answer;
    int re = 0;

    while (re < prog.size()) {
        for (int i = 0; i < prog.size(); i++) {
            if (prog[i] < 100 and prog[i] != -1) {
                prog[i] += speeds[i];
            }
        }
        
        int cnt = 0;
        for (int i = 0; i < prog.size(); i++) {
            if (prog[i] < 100) continue;
            if (i == 0 or (i != 0 and prog[i - 1] == -1)) {
                prog[i] = -1;
                cnt++;
            }
        }

        if (cnt) {
            answer.push_back(cnt);
            re += cnt;
        }
    }

    return answer;
}

 

2회차

- 반복문 한번으로 끝나는 코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prog, vector<int> speeds) {
    
    vector<int> answer;
    int maxDay = 0;
    for (int i = 0; i < prog.size(); i++) {
           
        int day = (99 - prog[i]) / speeds[i] + 1;
        if (answer.empty() || day > maxDay)
            answer.push_back(1);
        else
            answer.back()++;
        if (day > maxDay) maxDay = day;
    }
 
    return answer;
}