[프로그래머스 / Level2] 기능개발 (Java)

문제

https://programmers.co.kr/learn/courses/30/lessons/42586

코딩테스트 연습 - 기능개발

 

풀이 

제한사항

• n개의 기능 개선 작업을 진행한다.
• 각 기능은 진도가 100%일 때 서비스에 반영된다.(=배포)
• 각 기능의 개발속도는 모두 다르다. (기능 순서와 완료 순서는 다를 수 있음)
• 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 경우, 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포된다.
  = 어떤 기능이 먼저 완성되었더라도 앞에 있는 모든 기능이 완성되지 않았으면 배포 불가
  = 앞 작업의 필요작업기간 보다 뒤 작업의 필요작업 기간이 클 경우 같이 배포됨
• int[] progress : 각 기능의 작업 진도 (배포되어야 하는 순서대로 저장되어 있음)
• int[] speeds : 각 기능의 개발 속도
  = int[] progress, int[] speeds 의 배열 크기는 모두 같다.
• 각 배포마다 몇 개의 기능이 배포되는지를 int[] answer로 리턴하라.
  = int[] answer 배열 크기는 int[] progress, int[] speeds 의 크기보다 작거나 같다.
• 문제에서 구할 것은 '앞에서부터 해당 기능이 배포될 때 몇개의 기능이 함께 배포되는가?'

 

접근방식

기간, 작업량, 속도 등의 단어가 출현하는 것으로 보아 일률 공식을 이용해 원하는 값을 구할 수 있을 것 같다.

(일률) = (작업량) / (작업기간)  : 단위시간 동안 하는 일의 양
(작업기간) = (작업량) / (일률)  : 일률로 정해진 작업량을 완료하는데 걸리는 기간
(작업량) = (일률) x (작업기간)  : 일률로 정해진 기간동안 일했을 때 작업량

 

해당 문제를 푸는 데 필요한 것은 '각 작업이 완성되는데 걸리는 기간'이고, 주어진 값은 '각 기능의 현 작업 진도', '각 기능의 개발 속도'이다. '각 기능의 작업 진도'는 전체 작업량을 100으로 잡았을 때의 현재까지 진행된 작업량(%)이다. 즉, [전체 작업량 100 - 작업 진도 = 앞으로 해야하는 남은 작업량] 이라고 볼 수 있다. 이 값들을 위 일률 공식에 대입한다.

(각 작업이 개발되는데 필요한 기간) = (100 - 개발 진도) / (개발 속도)

 

문제에서 주어진 테스트케이스 [93, 30, 55] 에 위 공식을 적용해 각 작업이 개발되는데 필요한 기간을 구해보자.

작업	개발 진도	개발 속도	남은 개발 진도	(100- 개발 진도) / (개발 속도)
A	93	1	7	7/1 = 7
B	30	30	70	70/30 = 2
C	55	5	45	45/5 = 9

A, C 작업은 각각 7일, 9일 뒤 100%완료되는 것이 맞지만, B작업은 2일 뒤에 아직 개발 진도가 30 (+ 30 + 30) = 90으로 100%가 아니다. 이렇게 필요 기간이 잘 못 산출된 건 int타입 나누기 연산에서 소수점 자리가 잘려 내림됐기 때문이다. 70/30 = 2.333 에서 .333이 잘려 2가 나온 것. 우리는 70/30의 결과로 3이 나오기를 원한다.(B작업이 100%가 되는 건 3일 후이기 때문) 이를 위해서 나누기 연산에 사용되는 피연산자들을 double타입으로 변환해준 후 나누기 연산을 수행한 뒤 나온 결과를 올림해주자. 

(각 작업이 개발되는데 필요한 기간) = Math.ceil((double)(100 - 개발진도) / 개발 속도)

 

이렇게 구한 값은 Queue에 저장한다. progresses배열에서 앞에 위치하는 기능이 배포될 때 뒤의 기능이 함께 배포된다는 건, 뒤의 기능이 앞의 기능보다 먼저 배포되는 건 불가능하며 무조건 앞에 위치한(먼저 들어온) 기능 순으로 배포된다는 뜻이기 때문이다. 이는 FIFO(First In First Out) 구조의 Queue 특성과 잘 맞다.

 

코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        Queue<Integer> workDate = new LinkedList<>();       // 개발 기간
        ArrayList<Integer> release = new ArrayList<>();     // 배포당 기능 개수

        // 각 기능이 개발되기까지 남은 기간
        for (int i = 0; i < progresses.length; i++) {
            workDate.add((int)Math.ceil((double) (100 - progresses[i]) / speeds[i]));
        }

        int front = workDate.poll();
        int count = 1;

        while (!workDate.isEmpty()) {
            if (front < workDate.peek()) {  // 앞 기능보다 뒷 기능이 늦게 구현됨
                release.add(count);
                count = 1;
                front = workDate.poll();
            } else {                        // 앞 기능보다 뒷 기능이 먼저or동시에 구현됨
                count++;
                workDate.poll();
            }
        }
        release.add(count);                 // 마지막 값은 isEmpty 조건에 걸려서 별도 추가

        return release.stream().mapToInt(Integer::intValue).toArray();
    }
}

 

※ 아래와 같이 코드를 짜지 않도록 주의하자. [잘못된 예]

while (!workDate.isEmpty()) {
    if (front < workDate.peek()) {
        release.add(count);
        count = 1;
        front = workDate.poll();
    } else {
        count++;
        workDate.poll();
        front = workDate.poll();	// 잘못된 로직
    }
}