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

프로그래머스

 

풀이

 

1. Stack을 사용한 이유

맨 끝에 저장되어 있는 값을 뽑아와서 비교하면 O(1)의 시간이 소요되기 때문

 

2. 다른 사람들은 어떻게 코드를 짰는가

작업의 개수가 100개 이하여서, 배열의 길이를 100개만큼 만든 다음 for문 안에서 while문으로 확인해준 코드가 있었다. 그런데 이 경우에는 이중 포문을 사용한거나 다름이 없으니, 작업의 개수가 100개 이하일 때는 O(n^2)이여도 상관이 없지만 작업의 개수가 더 많아질 경우에는 시간복잡도 측면에서 비효율적일 것 같다.

 

나랑 비슷하게 접근해서 큐를 이용한 사람의 코드도 볼 수 있었다. 나는 개수를 cnt++로 계산해줬다면, 이 사람은 선입선출을 통해 더 오래 걸리는 작업이 들어올 경우 이전까지 저장해둔 큐의 size만큼을 배포해줬다.

 

3. Stack관련 문법 및 특징 등

이전에 적어둔 문제를 참고하면 될 것 같다.

[프로그래머스] 같은 숫자는 싫어 (JAVA)

 

 

전체코드

import java.io.*;
import java.util.*;

class Solution {
    public List<Integer> solution(int[] progresses, int[] speeds) {
        Stack<Integer> stack = new Stack<>();
        List<Integer> answer = new ArrayList<>();
        int cnt = 0;
        for(int i=0; i<progresses.length; i++){
            //배포까지 걸리는 시간 계산
            int day = (100 - progresses[i])/speeds[i];
            if(speeds[i]*day+progresses[i] < 100){
                day += 1;
            }
            if(stack.isEmpty()){
                stack.push(day);
            }else{
                int pre = stack.peek();
                if(pre < day){
                    answer.add(cnt+1);
                    cnt = 0;
                    stack.push(day);
                }else{
                    cnt++;
                    continue;
                }
            }
        }
        answer.add(cnt+1);
        return answer;
    }
}

 

cnt+1을 해주는 이유는, 배포 이후 카운팅을 해줄 때 첫번째 작업을 카운팅하지 않았기 때문이다.