[프로그래머스] 기능개발 (JAVA/자바)

문제

프로그래머스>코딩테스트 연습>고득점 Kit>스택/큐 : 기능개발 - https://programmers.co.kr/learn/courses/30/lessons/42586

풀이

맨 뒤의 기능부터, 각각의 기능이 끝나는데에 얼마나 걸리는지를 계산하여 스택에 쌓는다.

예를 들어,

• 1번 기능이 93% 완료되어있고 하루에 1%씩 작업이 가능하다면 7일 후 완료된다.
• 2번 기능이 30% 완료되어있고 하루에 30%씩 작업이 가능하다면 3일 후 완료된다.
• 3번 기능이 55% 완료되어있고 하루에 5%씩 작업이 가능하다면 9일 후 완료된다.

이 결과를 뒤 기능부터 스택에 쌓으면, 다음과 같이 쌓인다.
| 7 |
| 3 |
| 9 |
|___|

하루에 한번 배포하는데, 뒤에 있는 기능은 이미 완료되었더라도 앞의 기능이 배포될 때 같이 배포될 수 있다. 즉, 뒤에 있는 기능 중에 앞에있는 기능이 완료되기까지 걸린 일수보다 작거나 같은 일수가 걸렸다면 한번에 배포한다. 이 개념을 stack에 적용하여 하나를 pop()한 뒤(pop된 숫자가 리턴됨), stack을 peek(가장 위의 숫자를 참조만 함)했을 때, pop한 숫자보다 큰 수가 나올 때까지 pop을 진행한다.

위에서부터 7 5 4 3 9 10 7 6 이라는 숫자가 쌓여있다면, 7 5 4 3 / 9 / 10 7 6 으로 나뉘어 배포된다!!

코드

import java.util.ArrayList;
import java.util.Stack;

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

        Stack<Integer> stack = new Stack<>();
        for(int i=progresses.length-1; i>=0; i--){
            int progress = progresses[i];
            int speed = speeds[i];
            int day_cnt = 0;
            while(true){ // while문 한바퀴에 하루
                progress += speed;
                day_cnt++;
                if(progress>=100){
                    break;
                }
            }
            stack.push(day_cnt);
        }

        ArrayList<Integer> result = new ArrayList<>();
        while(!stack.isEmpty()){
            int cur = stack.pop();
            int cnt = 1;
            while(!stack.isEmpty() && stack.peek()<=cur){
                stack.pop();
                cnt++;
            }
            result.add(cnt);
        }

        int[] answer = new int[result.size()];
        for(int i=0; i<answer.length; i++){
            answer[i] = result.get(i);
        }
        return answer;
    }
}

정리

✔ 알고리즘 분류 - 스택/큐
✔ 난이도 - Level 2

🤦‍♀️ 메모

• 이런 유형의 문제는 스택을 활용해서 풀이할 수 있다는 걸 알아두기!

참고 사이트

딱히 없음