문제 설명
프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.
또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.
먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.
제한 사항
- 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
- 작업 진도는 100 미만의 자연수입니다.
- 작업 속도는 100 이하의 자연수입니다.
- 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.
입출력 예
progresse | speeds | return |
[93, 30, 55] | [1, 30, 5] | [2, 1] |
[95, 90, 99, 99, 80, 99] | [1, 1, 1, 1, 1, 1] | [1, 3, 2] |
입출력 예 설명
입출력 예 #1
첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다.
두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다.
세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다.
따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.
입출력 예 #2
모든 기능이 하루에 1%씩 작업이 가능하므로, 작업이 끝나기까지 남은 일수는 각각 5일, 10일, 1일, 1일, 20일, 1일입니다. 어떤 기능이 먼저 완성되었더라도 앞에 있는 모든 기능이 완성되지 않으면 배포가 불가능합니다.
따라서 5일째에 1개의 기능, 10일째에 3개의 기능, 20일째에 2개의 기능이 배포됩니다.
이번 문제를 푸는데 첨에 이해를 못했다. 하지만 문제를 자세히 읽어보고 나니 이해가 갔다.
이번 문제는 큐에 관한 문제이다.
왜냐하면 먼저 들어온애를 처리해야지 그 다음에 온애를 처리할수 있기 때문이다.
나는 que를 활용하기 위해
작업 속도를 담는 List
작업당 속도를 담는 List
이렇게 만들어서 각각 담았고
정답을 담는 List를 만들어서 정답을 담았다.
이제 소스를 한번 살펴보자.
import java.util.*;
class Solution {
public int[] solution(int[] progresses, int[] speeds) {
int[] answer = {};
//1. List에 모든 작업 담기
List<Integer> jobQue = new ArrayList<>();
for(int i = 0; i<progresses.length;i++){
jobQue.add(progresses[i]);
}
//2. List에 작업속도 담기.
List<Integer> speedQue = new ArrayList<>();
for(int i = 0; i<speeds.length;i++){
speedQue.add(speeds[i]);
}
//3. 배포개수 담는 List 생성
List<Integer> answerList = new ArrayList<>();
//4. 작업 list 비어 있을때까지 작업 계속 하기
while(!jobQue.isEmpty()){
int preSize = jobQue.size();
for(int i = 0;i<jobQue.size();i++){
//더한게 100 이상일때
if((jobQue.get(i)+speedQue.get(i) >= 100 && i == 0)){
jobQue.remove(i); //100이상인애 지운다.
speedQue.remove(i); //해당 작업에 맞는 작업속도도 없애준다.
//다음 remove하게 되면 다음 index 순서가 바뀌어서 que재진입해야함
i-=1; //index 순서 바뀐걸 넣기 위해
continue;
}else{
jobQue.set(i,jobQue.get(i)+speedQue.get(i)); //que의 작업 업데이트
}
}
if(preSize != jobQue.size()){ //que 확인 전과 후의 길이가 다를때 진입
answerList.add(preSize - jobQue.size());
}
}
answer = new int[answerList.size()];
for(int i = 0; i<answer.length;i++){
answer[i] = answerList.get(i);
}
return answer;
}
}
일단 작업속도 칸이 비어 있기 전까지 반복하는 while문을 만들었다.
그리고 그 presize라는 변수를 만들었다.
int preSize = jobQue.size();
이걸 만든 이유는
배포이전의 작업 개수랑 한번 배포 되고 나서의 남은 개수랑를 알기위해 만든거다
식으로 보자면 아래와 같다.
배포이전 - 배포이후 = 배포개수
이렇게 이전 크기를 만들고 나서는 이제 작업률이 100% 됐을때 List에서 제거해주는 걸 만들어야 한다.
그러기 위해 for문을 만들어서
작업 List 와 속도 List의 요소 접근을 해서
작업 + speed를 했다.
그래서 작업 + speed = 100 이 됐을때 지우는 작업을 해주었다.
if((jobQue.get(i)+speedQue.get(i) >= 100 && i == 0))
일단 둘이 더했을때 100이상이면 진입을 하는건 알거같은데 i==0일때 도 진입하는건 이해가 안갈수가 있다.
이걸 하는 이유는 우리가 사용하려는 것은 큐이기 때문이다.
그래서 항상 맨앞에 있는 요소만 제거가 가능하게 했다.
그럼이제 100이고 제일 앞에 있는 애일때 아래와 같이 제거해줬다.
jobQue.remove(i); //100이상인애 지운다.
speedQue.remove(i); //해당 작업에 맞는 작업속도도 없애준다.
내가 첨엔 작업만지웠다가 다른 테스트케이스에서 오류가 났는데 나중에 알고 보니까 작업속도도 지워줘야 한다는걸
알았다. 왜냐하면 작업만 지우게 돼면 작업에 맞지 않는 속도를 더해줄수 있기 때문에 지워줘야 한다.
그리고 이렇게 지우고 나서는 i 값을 -1 해주고 continue하게 했다.
//다음 remove하게 되면 다음 index 순서가 바뀌어서 que재진입해야함
i-=1; //index 순서 바뀐걸 넣기 위해
continue;
이렇게 하게 된 이유는 List는 순서가 있는거기 때문에 remove하게 되면 앞의 기존의 index가 -1씩 된다.
그래서 우리가 remove만 하고 바로 다음 list 요소에 접근을 하게 되면 한칸을 건너뛰고 검사하는거이기때문에
remove를 하고 나서는 i-=1 해서 다시 0부터 시작하게 하는것이다.
그래서 따지고 보면 우린 index가 0인애만 지우는거라고 볼수 있다.
이렇게 포문을 다 완료하고 나서는 뭔가 작업 List에 변동이 있다면 답 List를 추가해줘야 하는데 방법은 아래와 같다.
if(preSize != jobQue.size()){ //que 확인 전과 후의 길이가 다를때 진입
answerList.add(preSize - jobQue.size());
}
이렇게 다 완료 하고 나서는 answer 배열에 answerList 요소들을 집어넣었다.
느낀점
1. List는 remove하고 나서 index가 달라진다.
2. List와 Set은 .add() Map은 .put()
3. 문제를 진짜 자세히 살펴보자.
'코딩일기 > 알고리즘' 카테고리의 다른 글
[프로그래머스 : 레벨 2] 다리를 지나는 트럭 : Queue(Java) (0) | 2021.05.26 |
---|---|
[프로그래머스 : 레벨2] 프린터(java) (0) | 2021.05.22 |
[프로그래머스 : 레벨 3] 베스트 앨범 : List를 이용한 정렬(Java) (2) | 2021.05.21 |
[프로그래머스 레벨2] 위장 : HashMap 사용(Java) (0) | 2021.05.20 |
[프로그래머스 레벨2] 전화번호 목록 : HashSet사용(Java) (0) | 2021.05.20 |