[알고리즘 문제 풀이] 프로그래머스 - 기능개발

문제 원본 링크: programmers.co.kr/learn/courses/30/lessons/42586

카테고리: 스택/큐

 

문제 설명

프로그래머스 팀에서는 기능 개선 작업을 수행 중이다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포된다. 

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return하도록 solution 함수를 완성하라. 

 

제한 사항

• 작업의 개수(progresses, speeds 배열의 길이)는 100개 이하다.
• 작업 진도는 100 미만의 자연수이다.
• 작업 속도는 100 이하의 자연수이다.
• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정한다. 예를 들어 진도율이 95%인 작업의 개발속도가 하루에 4%라면 배포는 2일 뒤에 이루어진다.

 

입출력 예시

// 예시1
int[] progresses = {93, 30, 55};
int[] speeds = {1, 30, 5}; // return = {2,1}

// 예시2
int[] progresses = {95, 90, 99, 99, 80, 99};
int[] speeds = {1, 1, 1, 1, 1, 1}; // return = {1,3,3,1}

 

입출력 예시 설명

입출력 예#1

첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후에 배포가 가능하다.

두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능하다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일때 배포된다. 

세 번째 기능은 55% 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능하다.

 

따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포된다.

 

입출력 예#2

모든 기능이 하루에 1%씩 작업이 가능하므로, 작업이 끝나기까지 남은 일수는 각각5일, 10일, 1일, 1일, 20일, 1일이다. 어떤 기능이 먼저 완성되었더라도 앞에 있는 모든 기능이 완성되지 않으면 배포가 불가능하다.

 

따라서 5일째에 1개의 기능, 10일째에 3개의 기능, 20일째에 2개의 기능이 배포된다.

 

내 풀이

1. 배열을 순서대로 반복해서 완료되는데 걸리는 시간(days)를 구한다.
2. 구한 시간을 queue에 넣는다.
3. 큐를 while문으로 반복하여 값이 없을 때까지 한다.
4. 큐에서 꺼낸 값들이 가장 앞에 있는 값보다 작으면 함께 배포한다.
5. 새로 꺼낸 값이 가장 앞에 있는 값보다 크면 다음 배포 일정으로 넘어간다.
6. 큐에서 꺼낸 값이 앞에 있는 값보다 크고 마지막 값이라면 배포한다.

Java 코드

public int[] solution(int[] progresses, int[] speeds) {
        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < progresses.length; i++) {
            int progressRemain = 100 - progresses[i];
            int days = progressRemain / speeds[i];
            if (progressRemain % speeds[i] != 0) days += 1;

            queue.add(days);
        }

        int deploySum = 0;
        int bigDays = 0;
        List<Integer> answers = new ArrayList<>();

        while (!queue.isEmpty()) {
            int days = queue.poll();

            // 새 배포 일정 시작
            if (days > bigDays) {
                bigDays = days;

                // 이전에 계산된 일정을 답안에 추가
                if (deploySum != 0) answers.add(deploySum);
                deploySum = 1;

                // 마지막 값인 경우 답안에 추가
                if (queue.isEmpty()) {
                    answers.add(1);
                }
            } else {

                // 배포 개수 ++
                deploySum++;
                // 마지막 값인 경우 답안에 추가
                if (queue.isEmpty()) {
                    answers.add(deploySum);
                }
            }
        }

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

채점 결과

 

※ 실수한 것

처음 시도 점수는 27.3이었다. 문제를 잘못 이해했다. 예를 들어 10일 걸리는 일이 있고, 그 다음 5일, 6일 걸리는 일이 각각 있다면 6일 걸리는 일은 다음 배포 일정에 포함시켜야한다고 생각했다. 즉 뒤의 일들의 합이 앞에 있는 일의 일정보다 크면 안된다고 생각한 것이다. 잘못 이해한 탓에 시간이 더 많이 걸렸다. 

 

그리고 사실 내 풀이 방법은 굳이 queue를 사용하지 않아도 된다. 

 

다른 사람의 코드

public int[] solution2(int[] progresses, int[] speeds) {
        int[] dayOfend = new int[100];
        int day = -1;

        for(int i = 0; i < progresses.length; i++) {
            while (progresses[i] + (day * speeds[i]) < 100) {
                day++;
            }
            dayOfend[day]++;
        }
        return Arrays.stream(dayOfend).filter(i -> i != 0).toArray();
    }

내 코드에 비해 너무나 간결하다. 성능은 내 것과 비슷하다. 위 코드와 비교하면 내 코드는 참으로 단순하기 그지없는 방법을 사용했다. 반면 위 코드를 보면 어떻게 저렇게 생각할 수 있을까 재미있다. 배워야겠다. 가장 신박한 부분은 미리 크기가 100인 배열을 생성해놓고 for문과 while문 안에서 day와 배열을 사용해 순차적으로 값을 구하는 과정이다. 그리고 stream을 사용해서 배열 안에서 filter를 통해 0이 아닌 값만 추출해서 리턴했다. 

 

참고

깃허브 소스 코드: 링크