알고리즘 문제/Programmers
[프로그래머스] 기능 개발 - Java
Praetoriani
2021. 3. 20. 17:41
문제 : programmers.co.kr/learn/courses/30/lessons/42586
코딩테스트 연습 - 기능개발
프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는
programmers.co.kr
아이디어
현재까지의 진행도(progress)와 매일매일의 작업 진행량(speed)이 주어졌을 때, 이 기능이 배포될 때 까지 필요한 날짜는 다음과 같다.
ceil( (100 - progress) / speed )
각 작업이 위 식을 통해 구한 배포까지 필요한 날짜를 가지고 있게 하면 다음과 같은 방법을 통해서 쉽게 결과를 구할 수 있다.
- Queue를 만들고 전체 작업을 queue에 넣는다.
- Queue가 empty 될 때 까지 다음을 반복한다.
- 각 턴에는 Queue의 첫 번째 작업은 반드시 배포할 것이므로, 이 작업을 queue에서 poll하고, 카운팅한다 (count = 1)
- 이후 queue에 남아있는 작업들 중 방금 poll 해 준 작업보다 배포까지 필요한 날짜가 같거나 짧은 작업들을 모두 poll 하고, count를 증가시킨다.
- 더이상 같이 배포 가능한 작업이 없으면 이번 턴을 종료하고, 해당 count를 별도의 List에 저장한다.
- List에는 한 번에 배포 가능한 작업의 수 들이 저장되어 있다.
소스코드
import java.util.Queue;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
public class Main {
public int[] solution(int[] progresses, int[] speeds) {
// 1. Queue를 만들고 전체 작업을 넣는다.
Queue<Work> queue = new ArrayDeque<>();
for (int i = 0; i < speeds.length; i++) {
queue.offer(new Work(progresses[i], speeds[i]));
}
List<Integer> answers = new ArrayList<>();
// 2
while (!queue.isEmpty()) {
// 2-1. 매 턴 마다 배포 대기 큐의 첫 번째 기능은 배포한다.
int today = queue.poll().getDaysNeededToPublish();
int count = 1;
// 2-2. 같이 배포 가능한 기능 확인
while (!queue.isEmpty() && today >= queue.peek().getDaysNeededToPublish()) {
queue.poll();
count++;
}
// 2-3
answers.add(count);
}
// 3
return answers.stream().mapToInt(i -> i).toArray();
}
}
class Work {
private int currentProgress;
private int speed;
Work(int currentProgress, int speed) {
this.currentProgress = currentProgress;
this.speed = speed;
}
public int getDaysNeededToPublish() {
return (int)Math.ceil((100 - this.currentProgress) / (double)this.speed);
}
}