문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42586
문제 접근
1. 각 작업 진행 속도와 진행된 퍼센티지를 기반으로 배포까지 걸리는 일 수 계산
2. 배포 시작 기준이 되는 작업을 기준으로 전체 작업의 걸리는 일 수를 차감
3. 배포 시작 기준이 되는 작업부터 몇 개를 배포할 수 있는지 검사
4. 모든 작업이 배포될 때까지 1-3번 반복
문제 상황
문제 접근 3번을 잘 못 이해해서 좀 해맸었다.
내가 이해한 방식은 다음과 같다.
1번 작업 | 2번 작업 | 3번 작업 | 4번 작업 | 5번 작업 |
---|---|---|---|---|
완료 | 미완료 | 완료 | 완료 | 미완료 |
위와 같은 작업 상황일 때, 배포 될 수 있는 작업은 [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;
}
}
}
}
}
}