기능개발

Posted on Edited on In , ,

문제정의

먼저 배포해야하는 작업의 진행률과 작업속도가 주어진다. 뒤에 있는 개발이 완료되지 않더라도 앞순서의 개발이 완료되면 배포해야한다. 각 배포 시기마다 몇 개의 기능이 배포되는지 계산하는 문제이다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.*;

public class FunctionDevelope {

    //프로그래머스 level2 문제풀이 기능 개발
    
    public static void main(String[] args)
    {
        int[] progresses = {93, 30, 55};
        int[] speeds = {1, 30, 5};
        Queue<Integer> q = new LinkedList<>();
        ArrayList<Integer> answer = new ArrayList<>();
        int r_date;
        for(int i = 0; i < progresses.length; i++)
        {
            r_date = (int)Math.ceil((100-progresses[i])/(double)speeds[i]);
            q.add(r_date);
        }
        r_date = q.peek();
        int cnt = 0;
        while(!q.isEmpty())
        {
            if(r_date >= q.peek())
            {
                cnt++;
                q.remove();
            } 
            else
            {
                answer.add(cnt);
                cnt = 1;
                r_date = q.poll();
            }
            
        }
        answer.add(cnt);
    }
    
}
일단 각 기능이 언제 개발이 완료하는지 계산해야한다. 이 때, 배포는 하루의 끝에 완료된다는 가정이 있기 때문에 올림으로 처리해야한다. 정수간의 나눗셈은 정수만 반환하므로, 실수로 캐스팅하는 걸 잊어선 안된다. 그리고 큐에 완성일을 추가한다.

이 문제는 쉽게 큐에서 오름차순을 찾아내는 문제이다. 배포일 r_date를 큐의 첫번째 원소로 초기화한다. 그리고 배포되는 기능의 개수를 저장하는 cnt를 같이 선언한다. 큐에서 원소들을 보면서 r_date보다 빠른 것들은 같이 배포해야하는 것들이므로 cnt를 늘린다. 만약 r_date보다 늦게 배포하는 것은 배포일을 따로 하는 것이므로, 그 때 cnt를 어레이리스트에 저장하고 cnt를 1로 초기화한다. 비교할 r_date는 해당 원소로 업데이트한다.

이 문제의 시간복잡도는 큐에 들어갔다 나오는 최대 반복을 생각하면 된다. progresses의 길이를 n이라 했을 때, 총 삽입과 삭제의 수는 2n이다. 따라서 시간복잡도는 \(O(n)\)이 된다.

테스트



이 문제같은 경우 시간을 너무 많이 소요했다. 두번째 조건을 생각하기 힘들었는데, 질문하기에서 누군가가 올려준 테스트케이스 덕분에 통과할 수 있었다.