[프로그래머스][C++] 기능개발

기능개발

문제 링크

기능개발

분석

앞의 기능이 완료될 때까지 뒤의 기능은 배포되지 않습니다.

한 번에 몇 개의 기능이 배포되는지 배열을 만들어 반환해야합니다.

각 기능이 완료되는 날짜를 계산할 수 있습니다.
첫 번째 기능이 완료되는 날을 기준으로 이후 기능들의 완료 날짜와 비교하면서 한번에 배포할 기능들을 묶습니다.
첫 번째 기능보다 늦게 완료되는 기능이 나타나면 기존에 묶인 기능을 배포하고, 기준값을 변경합니다.
이 과정을 반복합니다.

풀이

브루트 포스(완전 탐색) 방식으로 푸는 방법입니다.

#include <vector>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    
    for (int i = 0; i < progresses.size(); ) // i는 배포를 기다리는 기능의 인덱스로 사용
    {
        // 한번에 배포할 개수 저장
        int count = 0;
        
        // j는 i부터 progresses를 순회
        for (int j = i; j < progresses.size(); ++j)
        {
            progresses[j] += speeds[j];
            
            // 현재 i번째의 배포가 준비된 경우
            if (progresses[i] >= 100)
            {
                ++count;
                ++i;                
            }
        }
        
        if (count != 0)
        {
            answer.push_back(count);
        }
    }
    
    return answer;
}

성능 요약

브루트 포스로 풀이한 성능은 다음과 같습니다.

시간 복잡도는 $O(n^2)$입니다.

• progresses를 순회하는 반복문 $O(n)$
• progresses를 i부터 순회하는 반복문 $O(n)$
• $O(n \times n)$

공간 복잡도는 $O(n)$입니다.

• 반환할 값을 저장하는 answer $O(n)$

테스트 1 〉 통과 (0.01ms, 4.44MB)
테스트 2 〉 통과 (0.02ms, 4.2MB)
테스트 3 〉 통과 (0.02ms, 4.13MB)
테스트 4 〉 통과 (0.01ms, 3.68MB)
테스트 5 〉 통과 (0.01ms, 4.07MB)
테스트 6 〉 통과 (0.01ms, 4.14MB)
테스트 7 〉 통과 (0.02ms, 4.21MB)
테스트 8 〉 통과 (0.01ms, 4.21MB)
테스트 9 〉 통과 (0.02ms, 4.21MB)
테스트 10 〉 통과 (0.02ms, 3.67MB)
테스트 11 〉 통과 (0.01ms, 3.68MB)