큐(Queue)를 활용한 알고리즘 문제풀이

오늘 푼 문제: 기능개발

• 입력: 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어집니다.
• 출력: 각 배포마다 몇 개의 기능이 배포되는지를 return합니다.

예제 코드

import java.util.*;

/**
 * 1. 큐에 작업들을 넣어두기 클래스로 만들어서 사용하기
 * 2. 큐에 대하여 loop를 돌며 선행 기능이 개발 되었을 때 몇일이 걸렸는지 확인
 * 3. 해당 기능이 배포 될 때 같이 배포되는 기능에 대하여 탐색
 */

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int[] answer = new int[]{};
        // 기능 개발을 도착순서에 따라 처리하기 위하여 Queue를 선언함
        Queue<Job> q = new LinkedList<>(); 
        for (int i = 0; i < progresses.length; i++) q.offer(new Job(progresses[i], speeds[i]));
        // 결과를 저장하기 위하여 List 선언
        List<Integer> result = new ArrayList<>();
        // 모든 큐에 대하여 loop가 돔
        while(!q.isEmpty()) {
        	// 해당 작업이 끝나기까지 필요한 시간을 구하는 코드
            Job cq = q.poll();
            int cnt = 1;
            int day = (int)Math.ceil((double)(100 - cq.progress) / (double)cq.speed);
            // 해당 작업이 끝날 때 완료되어있는 작업을 찾음. (입력 순서대로)
            while(!q.isEmpty() && q.peek().progress +  q.peek().speed * day >= 100) {
                q.poll();
                cnt++;
            }
            result.add(cnt);
        }
        answer = result.stream().mapToInt(Integer::intValue).toArray();
        return answer;
    }
    
    // 작업을 저장하기 위한 클래스 Job을 작성함.
    static class Job {
        int progress;
        int speed;
        
        public Job(int progress, int speed) {
            this.progress = progress;
            this.speed = speed;
        }
        
        @Override
        public String toString() {
            return  "[progress = " + progress + ", speed = " + speed + "]";
        }
    }
}

• 작업 클래스 Job을 생성하여 progress와 speed를 필드로 선언했어요.
• 작업의 경우 도착 순서대로 진행이 되어야하기 때문에 FIFO인 Queue를 활용해 봤어요.
• 매 loop마다 작업의 소요시간을 구한 뒤. q.peek()을 활용하여 다음 작업들 또한 끝나는지 확인해주었어요.

회고

• 오늘은 주석으로 구현 기능 정리도 했습니다.
• 형변환에 대해서 다시 한번 공부할 필요가 있다는 생각이 들었습니다.