문제링크

풀이

(100 - 작업진도) / 작업속도의 결과 값을 올림 연산하여, 각 작업이 완료되기까지 걸리는 일수를 계산한다.
이 값을 차례대로 큐(Queue)에 넣는다.

1. 큐의 가장 앞에 있는 값을 max 변수에 저장한다.

2. 이후 큐의 값을 peek() 메서드로 하나씩 확인하며,

   • max보다 작거나 같은 값은 같은 날 배포가 가능하므로 count++ 한다.
   • max보다 큰 값은 이후에 배포되어야 하므로,
     현재까지 누적된 count를 answer 리스트에 추가하고,
     max를 해당 값으로 갱신,
     count를 1로 초기화한다.

3. 큐가 비었을 경우, 마지막으로 누적된 count를 answer에 추가하고 종료한다.

주의할 점
작업 완료까지 걸리는 시간을 아래와 같이 계산할 경우:
(int)Math.ceil((100 - progresses[i]) / speeds[i])

• 100 - progresses[i]는 int - int 연산으로 정수 결과를 반환한다.
• 이후 speeds[i]로 나누는 연산도 정수 나눗셈이 되어 소수점 이하가 버려진다.
• 예를 들어, 실제로는 1.3일, 1.7일이 걸리는 작업도 1일로 계산되어 버그가 발생한다.

반례
입력값 〉 [99, 96, 94], [1, 3, 4]
기댓값 〉 [1, 2]
실행 결과 〉 [3]

해결 방법
100을 100.0으로 변경하여 연산 전체를 double로 유도해야 한다:
(int)Math.ceil((100.0 - progresses[i]) / speeds[i])

• 100.0 - progresses[i]는 double 타입으로 계산된다.
• 나눗셈 또한 double / int가 되어 소수점까지 정확히 계산된다.
• Math.ceil()은 올림 처리하여 정확한 작업 완료 일수를 구할 수 있다.

코드

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

class Solution {
    public ArrayList<Integer> solution(int[] progresses, int[] speeds) {
        ArrayList<Integer> answer = new ArrayList<>();
        
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < progresses.length; i++) { 
            q.offer((int)Math.ceil((100.0-progresses[i])/speeds[i]));
        }
        System.out.println(q);
        int max = q.peek();
        int count = 0;
        while(true){
            if(q.isEmpty()){
                answer.add(count);
                return answer;
            }
            int next = q.peek();
            if(next > max){
                max = next;
                answer.add(count);
                count = 0;
                continue;
            }
            q.poll();
            count++;
        }
        
    }
}