알고리즘 풀이 - 프로그래머스(기능개발, 큐)

 

문제 설명

 

기능 개선 작업을 수행 중인 프로그래머스에서 각 기능이 진도가 100%일 때, 서비스에 반영할 수 있다. 그러나 각 기능의 개발 속도는 모두 달라 뒤의 기능이 앞보다 먼저 개발될 수 있다. 아래의 정보가 제공된다

배열 progresses : 먼저 배포되는 순서대로 작업의 진도가 적힌 배열
배열 speeds : 각 작업의 개발 속도가 적인 정수 배열

 

제한 사항
 - 작업의 개수는 100개 이하
 - 작업 진도는 100 미만 자연수
 - 작업 속도는 100 이하 자연수
 - 배포는 하루에 1번만 가능, 하루의 끝에 배포 진행하여 95% 진행 중인 작업의 속도가 4%면 1일 후에는 99%, 2일 후에는 100%가 된 후 배포됨

 

예시

progresses	speeds	return
[93, 30, 55]	[1, 30, 5]	[2, 1]

첫 번째 기능은 93% 완료에 하루 1% 속도로 작업 가능 - 7일 후 배포
두 번째 기능은 30% 완료에 하루 30% 속도로 작업 가능 - 3일 후 배포
세 번째 기능은 55% 완료에 하루 5% 속도로 작업 가능 - 9일 후 배포

따라서, 7일 째에 1, 2번째 기능이 배포되고 9일 째에 3번째 기능이 배포 되어 각 배포 일자에 2개, 1개의 기능이 배포된다.

 

 

해결 방법1 - Stack / Queue를 혼합해서 진행

 

우선 반복문을 통해서 각 기능에 대해서 체크를 진행한다. 이 때, 각 기능의 완료 일자를 (100 - 현재 progress 값) % 작업 속도로 구할 수 있다. 해당 값을 A라고 할 때, 작업 속도로 나눈 A라는 값이 0보다 크다면 작업이 1일 더 필요하며, 0이면 해당 A일 후에 작업이 완료된다는 의미이다.

Stack은 현재 앞 기능이 완료될 때까지 진행되어야할 작업 목록이다. Stack이 비었거나 Stack의 0번째 값, 즉, 현재 시점에서 제일 먼저 배포되어야할 기능의 완료 일자가 현재 체크 중인 기능의 완료 일자보다 늦다면 Stack에 넣는다. 그렇지 않다면 현재 Stack에 쌓인 만큼이 특정 일자에 배포될 기능의 숫자이다.

Queue는 배포된 기능의 숫자를 담는다. Stack의 size만큼 담아서 배열로 변환한다. 이러한 logic을 바탕으로 아래 코드를 살펴보자.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
class Solution {
    public int[] solution(int[] progresses, int[] speeds){
        int[] complete = new int[progresses.length];
        Stack<Integer> stack = new Stack<>();
        Queue<Integer> queue = new LinkedList<>();
        for(int i=0; i < progresses.length; i++){
            // 완료될 일자 체크
            complete[i] = (100 - progresses[i]) % speeds[i] > 0 ? (100 - progresses[i]) / speeds[i] + 1: (100 - progresses[i]) / speeds[i];
            
            // Stack이 비었거나 가장 먼저 배포될 기능이 더 오래 걸린다면
            if(stack.isEmpty() || stack.get(0) >= complete[i]){
                stack.push(complete[i]);
                
            // 그렇지 않다면 Stack을 비우고 해당 size만큼을 queue에 넣는다.
            } else {
                queue.offer(stack.size());
                while(!stack.isEmpty()){
                    stack.pop();
                }
                stack.push(complete[i]);
            }
        }
        // 반복문 완료 후 남은 기능의 숫자를 Queue에 넣는다.
        queue.offer(stack.size());

        int answer[] = new int[queue.size()];
        int index = 0;
        
        // Queue의 값을 배열로 만들어 return
        while(!queue.isEmpty()){
            answer[index] = queue.poll();
            index++;
        }
        return answer;
    }
}

이 코드의 테스트 결과는 아래와 같다.

사실 이 코드는 처음에 생각해서 푼 방식인데 좀 이해가 어려운 듯 하다. 따라서 다른 방법으로도 풀어보았다.

 

 

해결 방법2 - Queue만 사용

 

아래의 코드를 우선 보자.

import java.util.LinkedList;
import java.util.Queue;
class Solution {
    public int[] solution(int[] progresses, int[] speeds){
        Queue<Integer> queue = new LinkedList<>();

        int arr_len = progresses.length;
        int index = 0;
        while(index < arr_len){
            int div = (100 - progresses[index]) / speeds[index];
            int mod = (100 - progresses[index]) % speeds[index];
            int d_day = mod > 0 ? div + 1 : div;

            int complete = 0;
            while(index < arr_len && progresses[index] + (speeds[index] * d_day) >= 100){
                index++;
                complete++;
            }
            queue.offer(complete);
        }

        int[] answer = queue.stream().mapToInt(Integer::intValue).toArray();
        return answer;
    }
}

 

이번에는 훨씬 짧은 코드로 구현하였다. Queue에는 완성된 기능들의 개수만 넣도록 구현한다. 반복문에서 현재 index에 해당하는 기능의 progress와 speed를 기반으로 완성일자를 계산한다. 현재 index번째 기능은 최우선순위이다.

그 일자를 바탕으로 차후의 모든 progress에 대해 그 일자 안에 해결된다면 모두 완성으로 간주하고, index 값을 늘려준다. 이 과정을 반복하면 최우선 순위의 완성 날짜를 계산하여 이후 배포될 기능들의 개수도 파악할 수 있다.

코드는 좀 더 짧았지만 아쉽게도 시간복잡도는 이전 보다 좋지 않았다. 다음의 테스트 결과로 확인할 수 있다.

 

 

다시 확인해보니, 2번째 방법은 answer 배열을 만들기 위해 stream을 사용했는데, 그것을 제외하고 1번째 방법으로 바꾸니 비슷한 결과가 나왔다. 아직 stream을 완전히 숙지하지 못해 추가 내용은 이후에 포스팅 해야겠다.