프로그래머스 - 큐 - 기능개발

programmers.co.kr/learn/courses/30/lessons/42586

코딩테스트 연습 - 기능개발

import java.util.*;

public class 기능개발 {
    public static void main(String[] args) {
        기능개발 o = new 기능개발();
        //System.out.println(Arrays.toString(o.solution(new int[]{93, 30, 55}, new int[]{1, 30, 5})));
        System.out.println(Arrays.toString(o.solution(new int[]{95, 90, 99, 99, 80, 99}, new int[]{100, 100, 100, 100, 100, 100})));
    }

    public int[] solution(int[] progresses, int[] speeds) {
        List<Integer> results = new ArrayList<>();

        int[] leftDays = new int[progresses.length];
        Queue<Integer> queue = new LinkedList<>();

        for(int i=0; i<progresses.length; i++) {
            leftDays[i] = (int)Math.ceil((100 - progresses[i]) / (double)speeds[i]);

            if(queue.peek() == null || queue.peek() >= leftDays[i]) {
                queue.offer(leftDays[i]);
            } else if(queue.peek() < leftDays[i]) {
                results.add(queue.size());
                queue.clear();
                queue.offer(leftDays[i]);
            }

            if(i == progresses.length-1) {
                results.add(queue.size());
            }
        }

        return results.stream().mapToInt(i->i).toArray();
    }
}

알고리즘

• 큐
• 해당 문제는 100에서 작업 진도를 빼고 작업 속도로 나누면 작업이 완료되기까지 남은 날짜를 알 수 있다.
• 단순하게 생각하면 남은 날짜를 한번의 순회로 구해놓고 남은 날짜를 다시 순회하여 한 번의 배포에 몇 개의 기능을 배포할 수 있는지 계산할 수 있다.(두 번 순회)
• 하지만 큐를 이용하면 한 번 순회를 통해 남은 날짜를 계산하면서 몇 개의 기능을 배포할 수 있는지 계산할 수 있다.
• 현재 계산된 남은날짜와 큐의 peek() 값과 비교하면서 경우에 따라 분기 처리를 해주면 된다.