문제 출처

코딩테스트 연습 > 스택/큐 > 기능개발
https://school.programmers.co.kr/learn/courses/30/lessons/42586

문제 설명

작업의 완료된 정도 progresses와 해당 작업을 처리할 때 속도 speeds가 주어진다. 작업의 남은 양을 계산하여 작업이 처리되는 일 수를 반환하라.

접근 방법

어떤 풀이를 하던 작업의 남은 일 수를 계산하는 계산식은
(100 - progress)/speed + (100-progress)%speed 한 것을 반올림한다.

1. stack을 이용한 풀이
   처음 풀 때는 stack을 이용해서 풀었다. 남은 일 수를 넣어두는 stack 그리고 작업이 처리되는 일 수 를 반환하는 day이다. stack에 남은 일 수를 계산하여 넣어 둔 뒤, pop하고, 해당 스택에서 peek하여 만약 이 전보다 작으면 스택에서 pop하여 제거하고 day를 1증가시킨다. 그렇게 계산된 일 수는 days에 push한다.

import java.util.Stack;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> days = new Stack<>();
        int remainingday;
        
        for(int i = progresses.length-1; i>=0; i--){
            remainingday = (100-progresses[i])/speeds[i];
                if((100-progresses[i])%speeds[i]>0){
                    remainingday++;
                }
            stack.push(remainingday);
        }
        
        while(!stack.isEmpty()){
            int day =1;
            int currentMax = stack.pop();
            while(!stack.isEmpty() && currentMax >=stack.peek()){
                stack.pop();
                day++;
            }
            days.push(day);
        }
        int[] answer = new int [days.size()];
        for(int j=days.size() -1 ;j>=0;j--){
            answer[j]=days.pop();
        }
        return answer;
    }
}

2. 배열만을 이용한 풀이
   배열만을 이용한 풀이도 접근 방식은 비슷하다. 현재 비교했던 것들 중 가장 큰 요소의 인덱스를 currentMax라 지정하고 이보다 작은 요소들을 만날 때는 day를 1씩 증가 시키고, 보다 큰 요소를 만나면 currentMax를 해당 인덱스로 지정하고 answer에 지금까지 증가시킨 day를 삽입한다. 그리고 다시 day는 1로 초기화 시킨다.
   이후 해당 과정이 끝나면 마지막으로 answer에 day를 삽입한다.(맨 마지막 day는 for문에서 반영이 안되기 때문)

import java.util.Stack;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        
        int answer[] = new int[progresses.length];
        int remain_day[] = new int[progresses.length];
        int i, j,currentMax, day;
        
        
        for(i = 0; i<progresses.length; i++){
            remain_day[i] = (100-progresses[i])/speeds[i];
            if((100-progresses[i])%speeds[i] >0 ) {
                remain_day[i] += 1;
            }
            
        }
        
        currentMax=0;
        j =0;
        day =1;
        for(i=1; i<remain_day.length; i++){
            if(remain_day[currentMax]>=remain_day[i]){
                day++;
            }else{
                currentMax = i;
                answer[j++] = day;
                day = 1;
            }
            
        }
        answer[j++] = day;
        
        int result[] = new int[j];
        for(i = 0; i<j; i++){
            result[i] = answer[i];
        }
        return result;
    } 
}

알게된 점

내가 푼 2가지 방식 모두 비슷한 흐름으로 풀린다. 물론 stack에서는 시간 복잡도가 O(n^2) (이중으로 while 문 사용)했고, 배열로 풀었을 때는 시간 복잡도가O(n)이다. 더 좋은 풀이 방법이 있겠지만, 내가 생각난 방법일 뿐이다.

문제푼 흔적

스택 풀이

배열 풀이