[알고리즘] 프로그래머스-기능개발

1. 문제

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

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

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

제한 사항

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

2. 나의 코드

풀이시간 : 1시간

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {

        List<Integer> answerList = new ArrayList();
        Queue<Integer> workQueue = new LinkedList();
        int size = progresses.length;

        for(int i=0;i<size;i++){
            Integer curProgress = progresses[i];
            workQueue.offer(curProgress);
        }

        int start = 0;
        while(!workQueue.isEmpty()){

            int completedNum = 0;

            for(int curIndex=start;curIndex<size;curIndex++){
                Integer curProgress = workQueue.poll();
                curProgress += speeds[curIndex];
                workQueue.offer(curProgress);
            }

            Integer frontNum = workQueue.peek();
            if(frontNum>=100){
                for(int curIndex=start;curIndex<size;curIndex++){
                    Integer curProgress = workQueue.peek();

                    if(curProgress>=100){
                        workQueue.poll();
                        start += 1;
                        completedNum += 1;
                    } else{
                        break;
                    }
                }
            }

            if(completedNum!=0)
                answerList.add(completedNum);
        }

        int[] answer = new int[answerList.size()];

        for(int i=0;i<answerList.size();i++){
            int x = answerList.get(i);
            answer[i] = x;
        }

        return answer;
    }
}

* 사용 자료 구조 : 큐

사용한 자료구조는 큐입니다. 큐를 사용해야겠다고 사용한 이유는 첫번째로 앞에 작업이 완료되야 뒤에 작업도 함께 배포될 수 있기 때문입니다. 바로 순서가 있다는 것 입니다. 1일 작업량을 현재 작업량에 계속 더하고, 맨앞의 작업량이 100% 이상이면 그날 배포할 개수를 구해줍니다.

3. 수정 코드

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        
        List<Integer> answerList = new ArrayList();
        Queue<Integer> workQueue = initWorkQueue(progresses);
        int size = progresses.length;
        
        int start = 0;
        while(!workQueue.isEmpty()){
            
            int completedNum = 0;
            
            Integer firstNum = workQueue.peek();
            int remainDay = getFirstRemainDay(firstNum, speeds[start]);
            
            for(int curIndex=start;curIndex<size;curIndex++){
                Integer curProgress = workQueue.poll();
                curProgress += speeds[curIndex]*remainDay;
                workQueue.offer(curProgress);
            }
            
            for(int curIndex=start;curIndex<size;curIndex++){
                Integer curProgress = workQueue.peek();
                if(curProgress>=100){
                    workQueue.poll();
                    start += 1;
                    completedNum += 1;
                } else
                    break;
            }
            
            if(completedNum!=0)
                answerList.add(completedNum);
        }
        
        int[] answer = getAnswerArray(answerList);

        return answer;
    }
    
    public Queue<Integer> initWorkQueue(int[] progresses){
        Queue<Integer> workQueue = new LinkedList();
        for(int i=0;i<progresses.length;i++){
            workQueue.offer(progresses[i]);
        }
        
        return workQueue;
    }
    
    public int[] getAnswerArray(List<Integer> answerList){
        int[] answer = new int[answerList.size()];
                for(int i=0;i<answerList.size();i++){
            answer[i] = answerList.get(i);
        }
        return answer;
    }
    
    public int getFirstRemainDay(Integer firstNum, int speed){
        int remainDay = (int)Math.ceil((double)(100-firstNum)/speed);
        return remainDay;
    }
    
}

기존 코드에서 개선사항은 하루 작업량을 계속 더하는 반복작업을 앞으로 몇일뒤에 첫번째 작업이 완료되는지 계산할 수 있기 때문에 남은 일 수 를 계산해서 1일 작업량에 곱해서 더해주었습니다. 이를 통해 속도를 향상 시킬 수 있었습니다.