[PCCP] Lv2: 기능개발(42586) 해설

문제

- 문제 링크: 기능개발

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 각 작업의 배포 가능일 구하기

2) 배포 가능일이 첫번째 작업일보다 빠르면 동시에 배포

3) 첫번째 작업일보다 늦은 작업일이 존재한다면 2번과정과 유사하게 해당 작업일 이후의 작업들을 묶어서 배포

4) 위의 과정 반복

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

- N: progresses의 길이

- day_left 벡터를 생성하기 위한 시간 복잡도: O(N)

- day_left의 각 요소를 한 번씩 순회할 때의 시간 복잡도: O(N)

- 최종 시간 복잡도: O(N)

#include <cmath>
#include <vector>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    int n = progresses.size();
    vector<int> days_left(n);
    
    // 작업별 완료까지 남은 일수 계산
    for (int i = 0; i < n; ++i) {
        days_left[i] = ceil((100.0 - progresses[i]) / speeds[i]);
    }
    
    int cnt = 0;  // 배포할 작업의 수
    int max_d = days_left[0]; // 현재 배포할 작업 중 가장 늦게 배포할 작업의 가능일
    
    for (int i = 0; i < n; ++i) {
        if (days_left[i] <= max_d) { // 배포 가능일이 가장 늦은 배포일보다 빠르면
            cnt++;
        } else { // 배포 가능일이 가장 늦은 배포일보다 느리면
            answer.push_back(cnt);
            cnt = 1;
            max_d = days_left[i];
        }
    }
    
    answer.push_back(cnt); // 마지막으로 카운트된 작업들을 함께 배포
    
    return answer;
}

solution 2)

- days[i] > max_val의 경우: val=1;의 위치 주의!

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    vector<int> days;
    
    int tmp = 0;
    int res = 0;
    for (int i = 0; i < progresses.size(); ++i){
        tmp = 100 - progresses[i];
        res = tmp % speeds[i];
        
        if (res == 0)
            days.push_back(tmp/speeds[i]);
        else if (res != 0)
            days.push_back(tmp/speeds[i] + 1);
    }
    
    
    int max_val = days[0];
    int val = 1;
    for (int i = 1; i < days.size(); ++i){
        if (days[i] <= max_val){
            val++;
        } else if (days[i] > max_val){
            max_val = days[i];
            answer.push_back(val);
            val = 1;
        }       
    }
    
    answer.push_back(val);
    
    return answer;
}

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: progresses의 길이

- daysLeft 배열을 생성하기 위한 시간복잡도: O(N)

- daysLeft의 각 요소를 한 번씩 순회: O(N)

- 최종 시간 복잡도: O(N)

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        Queue<Integer> answer = new ArrayDeque<>();
        
        int n = progresses.length;
        // 각 작업의 배포 가능일 계산
        int[] daysLeft = new int[n];
        for (int i = 0; i < n; ++i) {
            daysLeft[i] = (int) Math.ceil((100.0 - progresses[i]) / speeds[i]);
        }
        
        int count = 0; // 배포될 작업의 수 카운트
        int maxDay = daysLeft[0]; // 현재 배포될 작업 중 가장 늦게 배포될 작업의 가능일
        
        for (int i = 0; i < n; ++i) {
            if (daysLeft[i] <= maxDay) { // 배포 가능일이 가장 늦은 배포일보다 빠르면
                count++;
            }
            else {  // 배포 예정일이 기준 배포일보다 느리면
                answer.add(count);
                count = 1;
                maxDay = daysLeft[i];
            }
        }
        
        answer.add(count);  // 마지막으로 카운트된 작업들을 함께 배포
        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: progresses의 길이

- day_left 리스트를 생성하기 위한 시간복잡도: O(N)

- day_left의 각 요소 순회: O(N)

- 최종 시간 복잡도: O(N)

import math

def solution(progresses, speeds):
    answer = []
    n = len(progresses)
    
    # 각 작업의 배포 가능일 계산
    days_left = [math.ceil((100 - progresses[i]) / speeds[i]) for i in range(n)]
    
    count = 0 # 배포될 작업의 수 카운트
    max_day = days_left[0] # 현재 배포될 작업 중 가장 늦게 배포될 작업의 가능일 
    
    for i in range(n):
        if days_left[i] <= max_day: # 배포 가능일이 가장 늦은 배포일보다 빠르면
            count += 1
        else: # 배포 예정일이 기준 배포일보다 느리면
            answer.append(count)
            count = 1
            max_day = days_left[i]
            
    answer.append(count) # 마지막으로 카운트된 작업들을 함께 배포
    return answer

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: progresses의 길이

- daysLeft 배열 생성하기 위한 시간복잡도: O(N)

- daysLeft의 각 요소 순회: O(N)

- 최종시간복잡도: O(N)

function solution(progresses, speeds) {
    const answer = [];
    const n = progresses.length;
    
    // 각 작업의 배포 가능일 계산
    const daysLeft = progresses.map((progress, index) => Math.ceil((100 - progress) / speeds[index]));
    
    let count = 0; // 배포될 작업의 수 카운트
    let maxDay = daysLeft[0]; // 현재 배포될 작업 중 가장 늦게 배포될 작업의 가능일
    
    for (let i = 0; i < n; ++i) {
        if (daysLeft[i] <= maxDay) { // 배포 가능일이 가장 늦은 배포일보다 빠르면
            count++;
        } else { // 배포 예정일이 기준 배포일보다 느리면
            answer.push(count);
            count = 1;
            maxDay = daysLeft[i];
        }
    }

    answer.push(count); // 마지막으로 카운트된 작업들을 함께 배포
    return answer;
}

solution 2)

import

solution 3)

import