[프로그래머스] 기능 개발 - Java

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

코딩테스트 연습 - 기능개발

 

아이디어

현재까지의 진행도(progress)와 매일매일의 작업 진행량(speed)이 주어졌을 때, 이 기능이 배포될 때 까지 필요한 날짜는 다음과 같다.

        ceil( (100 - progress) / speed )

 

각 작업이 위 식을 통해 구한 배포까지 필요한 날짜를 가지고 있게 하면 다음과 같은 방법을 통해서 쉽게 결과를 구할 수 있다.

1. Queue를 만들고 전체 작업을 queue에 넣는다.
2. Queue가 empty 될 때 까지 다음을 반복한다.
   1. 각 턴에는 Queue의 첫 번째 작업은 반드시 배포할 것이므로, 이 작업을 queue에서 poll하고, 카운팅한다 (count = 1)
   2. 이후 queue에 남아있는 작업들 중 방금 poll 해 준 작업보다 배포까지 필요한 날짜가 같거나 짧은 작업들을 모두 poll 하고, count를 증가시킨다.
   3. 더이상 같이 배포 가능한 작업이 없으면 이번 턴을 종료하고, 해당 count를 별도의 List에 저장한다.
3. 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);
    }
}