기능개발

작성일: 2024-11-06

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42586

접근 방식

뒤의 작업이 먼저 끝나도, 앞의 작업이 끝나지 않으면 배포를 할 수 없다.

따라서, 앞의 작업이 완료되었을 때, 배포를 시작하고 뒤의 작업이 배포 가능한 상태인 경우에는 배포한다.

결과

소스 코드

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        List<Integer> answer = new ArrayList<>();
        int n = progresses.length;
        boolean[] visited = new boolean[n];
        int cnt = 0;
        while(cnt<n){
            int tmp = 0;
            for(int i=0; i<n; i++){
                progresses[i] += speeds[i];
            }
            for(int i=0; i<n; i++){
                if(visited[i]) continue;
                if(progresses[i]>=100){
                    visited[i] = true;
                    cnt++;
                    tmp++;
                }else{
                    break;
                }
            }
            if(tmp!=0) answer.add(tmp);
        }
        return answer.stream().mapToInt(a->a).toArray();
    }
}

먼저, 첫 번째 반복문에서 하루치 작업을 시작한다.

이후에, 두 번째 반복문에서는 배포 가능여부를 따지고, 배포가 가능한 경우 작업의 수를 센다.

마지막 if문에서는 배포 가능한 작업이 있다면 list에 추가해서 카운트를 한다.

다른 접근 방식

현재 내 코드는 하루씩 증가하면서 배포 가능한 작업들을 카운트하고있다.

하지만 한 번에 모든 작업들의 배포 가능 일을 계산해두고, 현재 날짜에서 배포 가능한 작업들을 카운트하는 방식도 있다.

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        List<Integer> answer = new ArrayList<>();
        int n = progresses.length;
        int day = 0;
        int count = 0;

        for (int i = 0; i < n; i++) {
            int remainWork = 100 - progresses[i];
            int daysNeeded = (remainWork + speeds[i] - 1) / speeds[i];

            if (daysNeeded > day) {
                if (count > 0) {
                    answer.add(count);
                    count = 0;
                }
                day = daysNeeded;
            }
            count++;
        }

        if (count > 0) {
            answer.add(count);
        }

        return answer.stream().mapToInt(i -> i).toArray();
    }
}

위 코드는 먼저, 현재 작업이 배포되는데 걸리는 날짜를 계산하고 있다.

그리고, 만약 현재 날짜보다 크고, count가 존재한다면(배포 가능한 작업이 있다면) answer에 추가하고 count를 0으로 초기화한다. day도 배포 가능한 날짜로 변경한다.

위 방식은 배포 가능한 날짜를 계산하고, 해당 날짜보다 크다면 카운트를 중단하고 answer에 추가하고, 가능하다면 계속 카운트를 해 가는 방식이다.

내가 풀었던 것과 마찬가지로 똑같이 O(n) 의 복잡도를 가지고 있지만, 한 번에 계산이 가능하다는 접근 방식을 통해 문제를 풀 수 있다.

알게 된 점

하루씩 증가하며 문제를 풀어도 되지만, 만약 한 번에 답을 구할 수 있는 상황이라면

문제에 따라서는 한 번에 구하는 것이 효율적일 수 있다.