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

스택 혹은 큐를 사용한 알고리즘 문제 입니다. (문제 확인 -> Click)

제한 사항

• 문제 요약 : n개의 작업 진도 및 속도가 주어질 경우, 몇번씩 배포되고 몇개의 기능이 배포되는지 배열로 출력
• 작업 개수 : 100
• 작업 진도 : 100미만
• 작업 속도 : 100이하
• ex. 배포는 하루에 한 번만 할 수 있고, 하루의 끝에 이뤄짐. 진도율이 95% 작업의 개발 속도가 하루의 1% 인 경우, 배포는 5일 뒤에 이뤄짐. 만약 두번째 기능이 3일 뒤에 이뤄진다 하더라도 1번째 기능이 완료되기 전까지는 배포할 수 없음

시도 방법

• 우선순위 큐 활용

Source

import java.io.*;
import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        ArrayList<Integer> list = new ArrayList<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < progresses.length; i++) {
            int remain = 100 - progresses[i];
            int count = remain % speeds[i] == 0 ? (remain / speeds[i]) : (remain / speeds[i]) + 1;
            if (pq.isEmpty()) {
                pq.add(count);
            } else {
                if (pq.peek() >= count)
                    pq.add(count);
                else {
                    list.add(pq.size());
                    pq.clear();
                    pq.add(count);
                }
            }
        }
        if (!pq.isEmpty())
            list.add(pq.size());
        return list.stream().mapToInt(i -> i).toArray();
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int pCount = Integer.parseInt(st.nextToken());
        int progresses[] = new int[pCount];
        int speeds[] = new int[pCount];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < pCount; i++)
            progresses[i] = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < pCount; i++)
            speeds[i] = Integer.parseInt(st.nextToken());

        int[] answer = solution(progresses,speeds);
        for (int i = 0; i < answer.length; i++)
            System.out.printf("%d ",answer[i]);

    }    
}