Programmers - 스택/큐 [기능개발]

1. 문제

문제 설명

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한 사항

• 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
• 작업 진도는 100 미만의 자연수입니다.
• 작업 속도는 100 이하의 자연수입니다.
• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

입출력 예

progresses                                     speeds                                          return

[93, 30, 55]	[1, 30, 5]	[2, 1]
[95, 90, 99, 99, 80, 99]	[1, 1, 1, 1, 1, 1]	[1, 3, 2]

입출력 예 설명

입출력 예 #1
첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다.
두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다.
세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다.

따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.

입출력 예 #2
모든 기능이 하루에 1%씩 작업이 가능하므로, 작업이 끝나기까지 남은 일수는 각각 5일, 10일, 1일, 1일, 20일, 1일입니다. 어떤 기능이 먼저 완성되었더라도 앞에 있는 모든 기능이 완성되지 않으면 배포가 불가능합니다.

따라서 5일째에 1개의 기능, 10일째에 3개의 기능, 20일째에 2개의 기능이 배포됩니다.

 

2. 내풀이

import java.util.*;

public class FunctionDev {
    public int[] solution(int[] progresses, int[] speeds) {
        ArrayList<Integer> finishDay = new ArrayList<>();
        ArrayList<Integer> answerList = new ArrayList<>();
        //각 progresses[i]를 speed[i]만큼 지나가게 한후 100이 달성 되면 몇일 걸리는 지
        //finishDay[i]에 저장
        for (int i = 0; i < progresses.length; i++) {
            // 작업한지 몇일이 지났냐?
            // 처음부터 1일이 지남
            int day = 1;
            // progresses[i]가 speeds[i]의 속도로 100이 넘을떄까지 증가시기고 넘으면 끝낸다.
            while (true) {
                progresses[i] += speeds[i];
                if (progresses[i] < 100) {
                    day++;
                } else {
                    finishDay.add(day);
                    break;
                }
            }
        }
        // progresses의 남은 일수들
        System.out.println(finishDay);

        // 배포할 갯수 , 처음에는 아무리 적어도 배포할 갯수는 1개 이상이므로 count = 1
        int count = 1;
        // 첫 progresses의 남은 일수
        int tmp = finishDay.get(0);
        // 두번째 progresses의 남은 일수 부터 tmp와 비교한다.
        for (int i = 1; i < finishDay.size(); i++) {
            // 남은 일수가 progresses[0]보다 클 경우 progresses[0]은 배포가된다.
            // 그리고 tmp는 progreses[0]보다 남은 일수가 많은 progress의 남은 일수가 된다.
            // 그리고 남은일수가 적은 것은 배포가 되므로 count = 0으로 초기화 된다.
            if (tmp < finishDay.get(i)) {
                answerList.add(count);
                tmp = finishDay.get(i);
                count = 0;
            }

            // tmp가 크던 말던 배포가능한 count횟수는 늘어난다.
            // tmp가 finishDay.get(i) 보다 작으면 대체된 tmp의 count는 1이 되어야 하므로 초기화의 의미
            // tmp가 finishDay.get(i) 보다 크거나 같으면 배포할 count는 늘어난다.
            count++;
        }
        // 반복문이 끝나고 배포해야할 갯수가 남았다면 배포한다.
        // 매우 중요하다. 마지막프로그램이 남았다면 배포해야한다.
        if (count > 0) answerList.add(count);

        // answer 옮겨 닮기
        System.out.println(answerList);
        int[] answer = new int[answerList.size()];
        for (int i = 0; i < answer.length; i++) {
            answer[i] = answerList.get(i);
            //System.out.println(answer[i]);
        }
        return answer;
    }

    public static void main(String[] args) {
        FunctionDev functionDev = new FunctionDev();
        int[] progresses = {99, 1, 55, 1, 1, 0};
        int[] speeds = {1, 30, 5, 1, 1, 1};
        System.out.println(functionDev.solution(progresses, speeds));
    }
}

- progress별로 남은 일수를 구한다음에 전의 남은일수가 더 작으면 배포 가능횟수를 늘리고 

전의 남은일수가 더 크면 배포를 해버린다. 그리고 끝에 나머지 배포가능한 것이 있으면 모두 배포 해버린다.

3. 다른사람 풀이

- 비슷하다..

4. Tip

- 먼저 남은 일수를 계산해야한다.

progress의 남은 일수를 잘보면 최대 최소값 구할 때 처럼 for문을 돌리는 것과 비슷하다.

1. progress의 남은 일수가 더 큰 값이 나올때까지 돌리면서 배포가능한 count가 증가한다,

2. progress값이 더 큰 값이 나온다면  배포하고 count를 0으로 초기화, 더 큰 값이 나온 progress는 더 큰 값이 나올

progress가 나올때까지 1.을 반복 

3. 다음 progress로 넘어가는것은 무조건 배포가능한 횟수가 늘어난다.

 

문제를 풀때 분석하며 종이로 먼저 풀어야겠다..

문제가 머리에 안들어온다.

 

JS

function solution(progresses, speeds) {
    var answer = [];
    let remainDays = [];
    // 남은 일수를 계산
    for(let i=0; i<progresses.length; i++){
        let day = 1;

        while(true){
            progresses[i] += speeds[i];
            if(progresses[i] < 100) day++;
            else {
                remainDays.push(day);
                break;
            }
        }
    }
    console.log(remainDays);
    let publish = remainDays[0];
    // 무조건 한개는 발표되므로
    let count = 1;
    for(let i=1; i<remainDays.length; i++){
        // 이전 제품이 개발된 날수가 더 적을 경우
        // 쌓여져 있던 제품들을 모두 발표
        if(publish < remainDays[i]){
            answer.push(count);
            count = 0;
            publish = remainDays[i];
        }
        count++;
    }
    // 만약 마지막에 개발된 제품이 남아있을경우
    if(count > 0) answer.push(count);
    return answer;
}

let progresses = [99, 1, 55, 1, 1, 0];
let speeds =  [1, 30, 5, 1, 1, 1]; 

console.log(solution(progresses, speeds));

- 문제는 풀었으나 꼼꼼하게 계산할 필요성이 크다.