99클럽 코테 스터디 8일차 TIL - [프로그래머스] 기능 개발 (Java)

📌 오늘의 학습 키워드

[프로그래머스] 기능 개발 (Java)
https://school.programmers.co.kr/learn/courses/30/lessons/42586

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : 먼저 배포되어야하는 순서대로 작업의 진도가 적힌 정수 배열 progresses, 각 작업의 개발. 속도가 적힌 정수 배열 speeds (1 ≤ progresses.length ≤ 100, 1 ≤ speeds.length ≤ 100)
출력 : 각 배포마다 배포되는 기능

가능한 시간복잡도

O(n)

알고리즘 선택

스택/큐

📌 코드 설계하기

1. 각 작업이 완료되는데 필요한 일수를 계산해 daysQueue에 저장한다.
2. 큐에서 작업을 하나씩 꺼내 현재 작업이 완료되는 일수(currentDay)를 기준으로, 그 이후의 작업들이 currentDay 이하의 일수 내에 완료되는 경우 그룹화한다.
3. 각 배포 그룹의 작업 수를 리스트에 저장 후, 배열로 변환해 반환한다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

없음

어떻게 해결했는지

없음

무엇을 새롭게 알았는지

queue.poll() : 큐의 첫 번째 요소를 반환만 하고, 삭제하지 않는다.

내일 학습할 것은 무엇인지

구현

📌 정답 코드

큐 풀이

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        List<Integer> result = new ArrayList<>();
        Queue<Integer> daysQueue = new LinkedList<>();
        
        for (int i = 0; i < progresses.length; i++) {
            int days = (int) Math.ceil((100.0 - progresses[i]) / speeds[i]);
            daysQueue.add(days);
        }
        
        while (!daysQueue.isEmpty()) {
            int currentDay = daysQueue.poll();
            int count = 1;
            
            while (!daysQueue.isEmpty() && daysQueue.peek() <= currentDay) {
                count++;
                daysQueue.poll();
            }
            
            result.add(count);
        }
        
        return result.stream().mapToInt(i -> i).toArray();
    }
}

스택 풀이

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        Stack<Integer> stack = new Stack<>();
        List<Integer> result = new ArrayList<>();
        
        for (int i = progresses.length - 1; i >= 0; i--) {
            int days = (int) Math.ceil((100.0 - progresses[i]) / speeds[i]);
            stack.push(days);
        }
        
        while (!stack.isEmpty()) {
            int currentDay = stack.pop();
            int count = 1;
            
            while (!stack.isEmpty() && stack.peek() <= currentDay) {
                count++;
                stack.pop();
            }
            
            result.add(count);
        }
        
        return result.stream().mapToInt(i -> i).toArray();
    }
}