[프로그래머스] 기능 개발

1. 문제

---

프로그래머스

2. 풀이 과정

---

진행상태와 진행속도를 알기 때문에 완료하는데 걸리는 시간을 알 수가 있다.

위의 예시 중 progresses = [95, 90, 99, 99, 80, 99], speeds = [1, 1, 1, 1, 1, 1] 인 경우 

각 기능이 완료하는데 걸리는 시간은 [5, 10, 1, 1, 20, 1]이다. 

5일이 되는 순간 1번 기능은 바로 배포된다. --> 1

10일이 되는 순간 2번, 3번 4번 기능이 동시에 배포된다. 3번, 4번 기능의 경우 2번 기능 때문에 기다려야 한다.  --> 3

20일이 되는 수간 5번, 6번 기능이 동시에 배포된다. 6번 기능의 경우 5번 기능 때문에 기다려야 한다. --> 2

 

정답: [1, 3, 2]

 

나는 이러한 과정을 큐를 사용해 해결했다.

 

• 일단 첫번째 기능을 큐에 넣는다.

• 두 번째 기능은 첫 번째 기능보다 오래 소요되므로 큐에 있는 첫번째 기능을 배포한 뒤 두 번째 기능을 큐에 넣는다.
• 답: [1]

• 세  번째, 네 번째 기능은 두 번째 기능보다 적게 소요 되므로 큐에 기능을 넣는다.

• 다섯 번째 기능은 두 번째, 세 번째, 네 번째 기능보다 오래 소요 되므로 이 세 개의 기능을 동시에 배포한 뒤
  다섯 번째 기능을 큐에 넣는다.
• 답: [1, 3]

• 여섯 번째 기능은 다섯 번째 기능보다 적게 걸리므로 큐에 넣는다.

• 더 이상 남은 기능이 없으므로 다섯 번쨰, 여섯 번째 기능을 동시에 배포한다.
• 답: [1, 3, 2]

최종 답은 [1, 3, 2]

3. 내 코드

---

import java.util.*;
class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int[] time_for_complete = new int[progresses.length];
        Queue<Integer> complete_queue = new ArrayDeque<>();
        List<Integer> release_cnt = new ArrayList<>();
        
        // 완료까지 남은 시간 계산하기 
        for(int i = 0; i < progresses.length; i++) {
            time_for_complete[i] = (int) Math.ceil((100.0 - progresses[i]) / speeds[i]);
        }
        
        for(int i = 0; i < time_for_complete.length; i++) {
            // 만약 큐에 저장된 첫 기능보다 더 오래 걸린다면 이는 배포해야 함
           if(!complete_queue.isEmpty() && time_for_complete[i] > complete_queue.peek()) {
                release_cnt.add(complete_queue.size());
                complete_queue.clear();
            } 
            
            // 큐에 기능 추가
            complete_queue.add(time_for_complete[i]);
        }
        
        // 큐에 남은 기능들 배포하기
        release_cnt.add(complete_queue.size());
        
        return release_cnt.stream().mapToInt(i -> i.intValue()).toArray();
        
    }
}

시간복잡도

• O(N)

Queue.clear()의 시간복잡도가 O(1)? (ChatGPT 답변)

일반적으로 ArrayDeque 를 사용하는 경우, clear() 메서드는 내부적으로 단순히 인덱스 포인터를 초기화하는 형태로 구현될 수 있습니다. 이렇게 되면, 이 작업의 복잡도는 O(1)이 됩니다.

4. 피드백

---

• 앞의 기능이 처리가 돼야 뒤의 기능이 나갈 수 있다는 점을 보고 큐를 떠올렸다.
• 자바에서 ArrayDeque를 사용하는 경우 clear()메서드는 O(1)의 시간복잡도가 소요된다.