PentaS

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42586

문제 접근

1. 각 작업 진행 속도와 진행된 퍼센티지를 기반으로 배포까지 걸리는 일 수 계산

2. 배포 시작 기준이 되는 작업을 기준으로 전체 작업의 걸리는 일 수를 차감

3. 배포 시작 기준이 되는 작업부터 몇 개를 배포할 수 있는지 검사

4. 모든 작업이 배포될 때까지 1-3번 반복

문제 상황

문제 접근 3번을 잘 못 이해해서 좀 해맸었다.

내가 이해한 방식은 다음과 같다.

위와 같은 작업 상황일 때, 배포 될 수 있는 작업은 [1번 작업, 3번 작업, 4번 작업]의 총 3개라고 생각했다.

하지만, 문제에서 요구한 카운팅 방식은 2번 작업이 아직 완료되지 않았기 때문에 1번 작업만 배포 될 수 있다.

즉, 완료된 작업이 연속적으로 나열되어있는 갯수를 카운팅 하는 것이었다.

소스 코드

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int[] answer = {};
        boolean[] isDone = new boolean[progresses.length]; //작업이 완료됐는지 체크하는 배열
        int[] remainDays = new int[progresses.length]; //작업이 몇일이나 걸리는지를 저장하는 배열
        List<Integer> releaseCount = new ArrayList<>(); //배포된 작업의 갯수를 저장하는 리스트

        //작업 속도와 진행된 퍼센트를 이용해 배포까지 몇일 걸리는지 계산
        for (int i = 0; i < remainDays.length; i++) {
            int remainPercent = 100 - progresses[i];
            remainDays[i] = remainPercent / speeds[i];
            if (remainPercent % speeds[i] > 0) {
                remainDays[i]++;
            }
        }

        int curIndex = 0;
        int nextIndex;
        do {
            checkDone(isDone, remainDays, curIndex); //기준 작업의 남은 일을 기준으로 작업량 차감 및 완료된 작업 체크

            nextIndex = findNextIndex(isDone, curIndex); //다음 배포되지 않은 작업 인덱스 탐색
            //배포될 수 있는 작업 수를 리스트에 저장
            if (nextIndex != -1) {
                releaseCount.add(nextIndex - curIndex);
            } else {
                releaseCount.add(progresses.length - curIndex);
            }
            curIndex = nextIndex;
        } while(curIndex != -1);

        //배포된 이력을 배열로 변환
        answer = new int[releaseCount.size()];
        for (int i = 0; i < releaseCount.size(); i++) {
            answer[i] = releaseCount.get(i);
        }
        return answer;
    }

    public int findNextIndex(boolean[] isDone, int curIndex) {
        for (int i = curIndex + 1; i < isDone.length; i++) {
            if (!isDone[i]) {
                return i;
            }
        }

        return -1;
    }

    public void checkDone(boolean[] isDone, int[] remainDays, int curIndex) {
        int stdDay = remainDays[curIndex];
        for (int i = 0; i < remainDays.length; i++) {
            if (!isDone[i]) {
                if (remainDays[i] > 0 && remainDays[i] <= stdDay) {
                    remainDays[i] -= stdDay;

                    if (remainDays[i] <= 0) {
                        isDone[i] = true;
                    }
                }
            }
        }
    }
}