[PGS] 기능개발 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

1. 단순 구현 (느리지만 구현하기는 더 쉬움)

import java.util.*;

class Solution {
    public List<Integer> solution(int[] progresses, int[] speeds) {
        Queue<Integer> q = new LinkedList<>();
        
        for (int i = 0; i < progresses.length; i++) {
            q.offer(i);
        }
        
        List<Integer> counts = new ArrayList<>();
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int now = q.poll();
                progresses[now] += speeds[now];
                q.add(now);
            }
            
            int cnt = 0;
            for (int i = 0; i < size; i++) {
                int now = q.peek();
                if (progresses[now] >= 100) {
                    q.poll();
                    cnt++;
                } else {
                    break;
                }
            }
            if (cnt > 0) {
                counts.add(cnt);
            }
        }
        return counts;
    }
}

2. 일률 공식을 이용한 구현 (효율이 더 좋음)

import java.util.*;

class Solution {
    public List<Integer> solution(int[] progresses, int[] speeds) {

        ArrayList<Integer> answer = new ArrayList<Integer>();
        Queue<Integer> q = new LinkedList<Integer>();

        // 일률 공식을 이용
        // 각 작업의 개발 기간 = (100 - 진도) / 개발 속도
        // 정수 값으로 들어가야 하고, 소수부분이 존재하면 하루가 더 필요한 것이므로, 소숫점 올림을 해서 넣어준다.
        for (int i = 0; i < progresses.length; i++) {
            q.add((int) Math.ceil((100.0 - progresses[i]) / speeds[i]));
        }

        while (!q.isEmpty()) {
            int minDays = q.poll();
            //해당 일자에 배포되는 총 기능의 수를 담기 위한 변수, int count를 1로 선언 및 초기화
            int count = 1;

            while (!q.isEmpty() && q.peek() <= minDays) {
                q.poll(); 
                count++;
            }

            answer.add(count);
        }

        return answer;
    }
}

📄 해설

• 풀이 1이 작성자가 해결한 방법이다.
• 다른 풀이도 한번 찾아보던 중에 대부분의 풀이가 풀이 2와 같다는 것을 확인했고, 둘의 효율성을 비교해보니, 풀이 2의 효율성이 더 높아 두 방법 모두 업로드해보았다.
• 엄청나게 큰 차이는 아니긴한데, 이런 수식을 사용하는 풀이가 아직 좀 미숙하다.

풀이 1 접근 및 과정

• 큐를 사용하고, 문제에서 제시한 조건에 맞춰서 구현하였음
• 각 기능들의 인덱스를 큐에 넣고, 큐가 빌 때까지 아래 과정을 반복한다.
  • 각 기능들을 큐에서 꺼내서 개발속도 만큼 개발 진도를 증가시킨다.
  • 큐를 순회하면서 큐에서 제일 앞에 있는 기능이 끝났으면 큐에서 제거한다. 이때, 제일 앞의 기능이 안 끝났으면 반복을 종료한다.
  • 끝난 기능의 개수를 정답 리스트에 추가한다.

풀이 2 접근 및 과정

• 일률 공식을 이용한다. 일률 공식에서 각 기능의 개발 기간은 아래와 같다.
  각 기능의 개발 기간 = (100 - 진도) / 개발 속도
• 위 공식을 코드에 적용하면 아래와 같다.
  각 기능의 개발 기간 = (int) Math.ceil((double) (100 - 진도) / 개발 속도)
• 이렇게 구한 각 개발 기간을 전부 큐에 넣고, 큐가 빌때까지 아래 과정을 반복한다.
  • 큐에서 숫자 하나를 꺼낸다. (가장 앞 기능 개발이 끝날때까지 걸리는 기간이다.)
  • 큐가 비어있거나 현재 최소 기간인 minDays 보다 현재 큐의 첫번째 원소가 더 크면 반복을 종료한다.
  • 큐가 비어있지 않고, 현재 최소 기간보다 현재 큐의 첫번째 원소가 더 작으면 큐에서 꺼내고, 개수인 count 를 증가시킨다.
  • 반복이 끝났다면 완료 작업 개수인 count 를 answer 에 추가한다.