프로그래머스 알고리즘 고득점 kit 스택/큐 - 기능개발

문제 요약

• 각 기능의 개발 진도는 정수로 주어지며 모든 기능은 매일 일정한 속도로 개발된다.
• 기능은 앞에 있는 기능이 완성되어야 함께 배포된다.
• 각 기능별로 완성까지 필요한 일수를 계산하고, 하루에 몇 개의 기능이 함께 배포되는지를 구해야 한다.

입력 예시

progresses = {93, 30, 55};
speeds = {1, 30, 5};

출력 예시

[2, 1]

• 첫째 날: 7일 뒤 첫 번째와 두 번째 기능이 완성 → [2]
• 이후 9일째에 세 번째 기능이 혼자 완성 → [1]

---

알고리즘 설계

1. 각 기능이 완성되기까지 걸리는 날짜를 계산한다.
   • (100 - progresses[i]) / speeds[i] (나누어 떨어지지 않으면 하루 더 필요)
2. 계산된 날짜를 순서대로 Queue에 넣는다.
3. Queue를 순회하며 앞의 기능보다 작거나 같은 날짜면 같은 날 배포 가능 → 개수 누적
4. 더 큰 날짜가 나오면 → 새로운 배포 시작

---

전체 코드

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        List<Integer> answer = new ArrayList<>(); // 결과 저장용 리스트
        Queue<Integer> q = new LinkedList<>();    // 기능별 완료까지 필요한 날짜

        // 1. 각 기능마다 완료까지 걸리는 날짜 계산
        for (int i = 0; i < progresses.length; i++) {
            int duration = (100 - progresses[i]) / speeds[i];
            if ((100 - progresses[i]) % speeds[i] > 0) duration++; // 나머지 있으면 하루 추가
            q.offer(duration); // 큐에 넣기
        }

        int beforeDuration = q.poll(); // 첫 번째 작업일수 기준
        answer.add(1); // 첫 배포는 무조건 1개 시작

        // 2. 큐 순회하며 배포 그룹 계산
        while (!q.isEmpty()) {
            int currentDuration = q.poll();
            
            if (beforeDuration >= currentDuration) {
                // 현재 작업도 이전 작업과 함께 배포 가능
                int last = answer.get(answer.size() - 1);
                answer.set(answer.size() - 1, last + 1);
            } else {
                // 더 오래 걸리는 작업은 새로운 배포 시작
                answer.add(1);
                beforeDuration = currentDuration;
            }
        }

        // 3. 결과 리스트를 배열로 변환
        return answer.stream().mapToInt(i -> i).toArray();
    }
}

---

시간복잡도

• O(N) : progresses의 길이만큼 한 번 순회