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

문제 링크

1. 문제 해결

제한 사항

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

제한 사항에서 빨간색인 부분을 주의하자.

1-1. 전처리

알고리즘을 진행하기 위해 클래스 정의가 필요한데 아래와 같은 변수를 저장하는 클래스를 선언한다.

• 작업이 종료되는 일 (finish)
• 함께 배포될 작업들 (count)

1-2. 알고리즘 진행

정의한 클래스를 자료형으로 담는 큐를 생성한 후, 알고리즘을 진행하면 된다.
👉 위에서 언급한 대로 빨간색으로 표시한 제한 사항을 생각하길 바란다.

정확하게 배열의 크기를 알 수 없어 우선 리스트를 거쳐 최종적인 배열의 크기를 구한 후, int 배열에 리스트 값을 할당하여 반환한다.

2. 소스 코드

import java.util.*;
class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        Queue<Progress> q=  new LinkedList<>();
        List<Integer> temp = new ArrayList<>();
        for(int i =0 ; i < progresses.length ; i++){
            int cur_p = progresses[i];
            int cur_s = speeds[i];
            
            
            int remain = 100 - cur_p;
            int finish_day = remain / cur_s;
            int mod = remain % cur_s;
            
            if(mod > 0)
                finish_day ++;
            
            
            if(q.isEmpty()){
                q.add(new Progress(finish_day,1));
            }else{
                if(q.peek().finish >= finish_day){
                    //첫 작업이 오래 걸리는 경우
                    q.peek().count += 1;
                }else{
                    temp.add(q.poll().count);
                    q.add(new Progress(finish_day,1));
                }
            }
        }
        
        if(!q.isEmpty())
            temp.add(q.poll().count);
        
        int [] ret = new int[temp.size()];
        
        for(int i =0 ; i < ret.length;  i++){
            ret[i] = temp.get(i);
        }
        
        return ret;
    }
    
    private class Progress{
        int finish, count;
        
        public Progress(int f, int c){
            this.finish = f;
            this.count= c;
        }
    }
}