[프로그래머스] 기능개발 (시뮬레이션)

문제 소개

오늘 풀었던 프로그래머스 - 기능개발 문제를 정리합니다.

이 문제는 여러 작업의 진도(progresses)와 개발 속도(speeds)가 주어졌을 때,
각 작업이 몇 일 후 완료되는지 계산하고, 앞 작업이 끝날 때 함께 배포될 수 있는 뒤 작업들을 묶어서, 각 배포마다 몇 개의 기능이 배포되는지를 구하는 문제입니다.

문제 링크: 기능개발 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 각 작업이 완료되는 날짜를 계산한다
   → (100 - progresses[i] + speeds[i] - 1) / speeds[i]
2. 순서대로 작업을 확인하면서,
   • 가장 앞의 작업보다 늦게 끝나는 작업이 나오면 배포 단위 마감
   • 같은 날 또는 더 빨리 끝나는 작업들은 같은 배포 묶음으로 처리
3. 각 배포마다 포함된 기능 수를 카운트해서 리스트로 반환한다

---

해결 과정 및 코드

핵심 아이디어

1. 각 작업의 완료 날짜를 기준으로 앞 작업이 끝날 때 함께 배포 가능한 뒷 작업까지 묶는다
2. dayOfend[] 배열을 활용해 날짜별 배포 수를 카운트 (최대 길이 100으로 제한)

코드

시간 복잡도 : O(N)

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int[] dayOfend = new int[100];
        int day = -1;

        for (int i = 0; i < progresses.length; i++) {
            while (progresses[i] + (day * speeds[i]) < 100) {
                day++;
            }
            dayOfend[day]++;
        }

        return Arrays.stream(dayOfend).filter(i -> i != 0).toArray();
    }
}

 

---

Queue로 해결할 경우 

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        
        // Step 1: 각 작업의 완료일 계산
        for (int i = 0; i < progresses.length; i++) {
            int remain = 100 - progresses[i];
            int days = (remain + speeds[i] - 1) / speeds[i]; // 올림 처리
            queue.offer(days);
        }

        List<Integer> result = new ArrayList<>();
        
        // Step 2: 배포일 확인
        while (!queue.isEmpty()) {
            int current = queue.poll();
            int count = 1;
            
            // 뒤에 있는 작업들이 앞 작업과 같이 배포될 수 있는지 확인
            while (!queue.isEmpty() && queue.peek() <= current) {
                queue.poll();
                count++;
            }
            result.add(count);
        }

        // 결과 변환
        return result.stream().mapToInt(Integer::intValue).toArray();
    }
}