허성현

허성현

현재에 안주하지 않고 꾸준히 노력하는 개발자입니다.

[고득점 kit] - 기능 개발

업데이트:

Programmers - 42586

문제 설명

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

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

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

제한 사항

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

입출력 예

progresses speeds return
[93, 30, 55] [1, 30, 5] [2, 1]
[95, 90, 99, 99, 80, 99] [1, 1, 1, 1, 1, 1] [1, 3, 2]

생각해보자!

배포는 하루에 한 번만 할 수 있고 먼저 개발되었더라도 앞에 기능이 구현되지 않았다면 먼저 배포(dequeue)될 수 없는 구조이기 때문에 FIFO(First In First Out) 구조인 Queue 로 구현하는 것이 적당하다고 생각했다. 그렇다. 여기까지는 누구나 생각할 수 있다.

차근차근 코딩해보기!

  1. 기능별로 남은 기간들(remainingPeriods)을 계산해서
  2. 배포 일(releaseDate)을 구하고 큐에 차례대로 넣은 다음
  3. 큐의 fornt에 있는 기간을 기준으로 더 오래 걸리는 시간을 찾으면
  4. 앞 기능들을 모조리 배포(dequeue)한다.
  5. 2~4을 반복한다.

결국 각 기능들의 배포 일을 구해서 비교하고 더 오래 걸리는 기능이 있다면 그 기능 앞에서 구현이 완료된 기능들을 배포하면 된다.

Step1. 배포일을 구해보자

  • remainingPeriods(남은 기간) = (100 - progresses)

  • releaseDate(배포 일) = remainingPeriods / speeds

여기서 주의 할 점은 배포는 하루의 끝에 이루어진다고 가정했기 때문에 만약, 기능 구현이 2.3일이 걸린다고 한다면 배포는 3일 뒤에 할 수 있다는 것을 명심해야 한다. 그러면 조건을 어떻게 해주어야 할까? 많은 방법이 있겠지만 나머지를 이용해서 배포일(releaseDate)이 나누어 떨어지지 않으면 +1을 해주는 방법이 가장 먼저 떠올랐다.

1
2
3
4
5
6
7
8
9
10
11
12

// 배포일을 담을 큐 생성
Queue<Integer> releaseDate = new LinkedList<Integer>();
// 배포일을 구해서 큐에 담아보자.
for(int i = 0; i < progresses.length; i++) {
		int remainingPeriods = 100 - progresses[i];	// 남은 기간
  	// 배포일이 나누어 떨어지지 않으면 +1일을 해준다.
  	if(remainingPeriods % speeds[i] != 0) {
				releaseDate.add((remainingPeriods / speeds[i]) + 1);
  	} else {
    		releaseDate.add(remainingPeriods / speeds[i]);
  	}
}

+1 일을 해주는 이유

정수 형태는 소수점 이하의 수를 버리기 때문이다. 예를 들어 2.1~2.9일은 전부 2일로 취급되기 때문에 +1일을 해주어서 조건을 맞춰줘야 한다.

다른 방법으로는 Math.ceil() 함수를 사용해서 올림을 해주는 방법도 있다.

주의 할 점은 remainingPeriods(정수) / speeds(정수) = (정수) 이기 때문에 Math.ceil()함수로 올림을 하려고 해도 먹히지 않는다. 이럴 때에는 아래와 같이 한 쪽을 실수로 형변환 해준다.

1

releaseDate = (int)(Math.ceil(remainingPeriods / (double)speeds));

1
2
3
4
5
6
7

for (int i = 0; i < progresses.length; i++) {
		int releaseDate;
  	int remainingPeriods = 100 - progresses[i];
  	// Math.ceil() 메서드를 이용해서 배포일 구하기
  	releaseDate = (int) Math.ceil(remainingPeriods / (double) speeds[i]);
  	queue.add(releaseDate);
}

토막 상식 : Math 클래스의 메서드

method return fucntion
round(double / float a) long / int 반올림
ceil(double a) double 올림
floor(double a) double 버림
abs(double / float / int / long a) double / float / int / long 절댓값

위와 같은 방법으로 아래 테스트 케이스의 배포일을 구해보자.

progresses speeds releaseDate
[95, 90, 99, 99, 80, 99] [1, 1, 1, 1, 1, 1] [5, 10, 1, 1, 20, 1]

Step2. 배포되는 기능 카운트하기

배포되는 기능을 카운트하기 위해서는

  1. 가장 먼저 배포되어야 할 기능의 배포일(큐의 peek)을 기준일(compValue)로 잡고
  2. 기준일과 각각의 배포일을 비교해서
  3. 기준보다 작으면 개발이 완료된 기능이므로 배포(poll) 하고 count한다.
  4. 기준보다 크면 아직 개발이 덜 된 기능이므로 배포를 멈추고, 현재까지 배포된 기능의 수(count)를 저장한다.
  5. 전부 배포 될 때까지 1~4를 반복한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// 카운트된 결과를 담을 리스트 생성
ArrayList<Integer> result = new ArrayList<Integer>();

// 전부 배포 될 때까지 반복한다.
while (!releaseDate.isEmpty()) {
  	int count = 0;
  	int compValue = releaseDate.peek(); // 큐의 front를 기준으로 잡는다.
  	// 배포할 기능이 있고 & 기준 배포일이 
  	while (!releaseDate.isEmpty() && compValue >= releaseDate.peek()) {
    		releaseDate.poll();
    		count++;
  	}
  	// 그러다가 기준보다 큰 수를 만나면 배포를 멈추고 카운트 된 수를 결과 리스트에 저장한다.
  	result.add(count);
}

두 번째 while 문에서 !releaseDate.isEmpty() 조건의 의미

  • 만약 남아있는 모든 기능의 배포일이 기준 배포일보다 작다면 계속 배포되므로
  • 전부 다 배포되었을 때(큐가 비었을 때) 없는 기능이 배포되지 않도록 예외처리를 해주어야 한다.
  • 그렇지 않는다면 컴파일 시 NullPointException 에러가 발생한다.

Step3. 결과 값 복사

기능들이 전부 배포가 되었고 배포된 기능들의 카운트가 완료되었다면

답안지 배열(answer)에 deepcopy해서 리턴하자.

1
2
3
4
5
6

// 결과를 리턴할 리스트 선언
int[] answer = new int[result.size()];
// deepcopy
for (int i = 0; i < answer.length; i++) {
  	answer[i] = result.get(i);
}

회고

처음 내 아이디어는 대략 이랬다.

  1. 개발중인 기능을 큐(function)에 넣는다.
  2. 넣을때 배포기간을 계산해서 releaseDate 리스트에 저장한다.
  3. 따로 카운트(count) 배열을 두고 3가지 케이스를 비교해서
  4. 각 경우마다 기능을 배포하고 카운트를 증가시켜준다.

이렇게 하다 보니 비교해야 할 케이스가 너무 많이 생겨서 if~else 구문을 남발해야 했다. 결정적으로 모든 테스트 케이스를 통과하지 못했다. 결국, 나와 가장 비슷한 생각으로 해결한 다른 개발자분들의 아이디어를 참고해서 문제를 끝까지 풀 수 있었다. 생각지도 못한 접근들도 많이 봤지만 가장 직관적인 접근부터 확실하게 구현할 줄 알아야 한다고 생각했다. 문제 해결의 포인트는 개발 중인 기능이 아닌 배포일(releaseDate)에 포커스를 두는 것이었다.

이 문제를 완벽하게 이해하고 정리하는데 반나절은 넘게 걸린 것 같다. 다들 ‘이 정도면 쉬운 편!’이라고 해서 조금은 절망스러웠지만 이 문제를 발판 삼아 앞으로 열심히 성장해야겠다.

FunctionDevelop.java

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
40
41
42
43
44
45
46
47
48

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

public class FunctionDevelop {

	public static int[] solution(int[] progresses, int[] speeds) {
		// Step1. 배포일 구해서 큐에 담기.
		Queue<Integer> releaseDate = new LinkedList<Integer>();
		for (int i = 0; i < progresses.length; i++) {
			int remainingPeriods = 100 - progresses[i];
			if (remainingPeriods % speeds[i] != 0) {
				releaseDate.add((remainingPeriods / speeds[i]) + 1);
			} else {
				releaseDate.add(remainingPeriods / speeds[i]);
			}
		}
		// Step2. 배포일 비교와 카운트
		ArrayList<Integer> result = new ArrayList<Integer>();
		while (!releaseDate.isEmpty()) {
			int count = 0;
			int compValue = releaseDate.peek();
			
			while (!releaseDate.isEmpty() && compValue >= releaseDate.peek()) {
				releaseDate.poll();
				count++;
			}
			result.add(count);
		}
		// Step3. deepcopy
		int[] answer = new int[result.size()];
		for (int i = 0; i < answer.length; i++) {
			answer[i] = result.get(i);
		}

		return answer;
	}

	public static void main(String[] args) {
		
		int[] progresses = { 50, 90, 80, 20, 80, 99 };
		int[] speeds = { 1, 1, 1, 1, 1, 1 };
		int[] answer = solution(progresses, speeds);

		System.out.println(Arrays.toString(answer));
	}
}

참고