[프로그래머스] 야근 지수 Java 풀이

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다.Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요.

2. 입력

• works는 길이 1 이상, 20,000 이하인 배열입니다.
• works의 원소는 50000 이하인 자연수입니다.
• n은 1,000,000 이하인 자연수입니다.

3. 예제

works	n	result
[4, 3, 3]	4	12
[2, 1, 2]	1	6
[1,1]	3	0

4. 풀이

문제를 풀기에 앞서 문제 이해가 쉽도록 정리를 하자면 N시간 동안 일을 하여 Works 배열에 있는 여러 일의 수치를 낮추어 남은 Works의 일의 지수 제곱의 합이 최소화 되도록 하는 것입니다.

 

만약 Worksrk [5, 8, 1]이며 N이 1인 경우

• 5의 일을 1시간하여 4로 만들면 4 * 4 + 8 * 8 + 1 * 1이 야근 지수가 되며 이 값은 81이 됩니다.
  
  
• 8의 일을 1시간하여 7로 만들면 5 * 5 + 7 * 7 + 1 * 1이 야근 지수가 되며 이 값은 75가 됩니다.
  
  
• 1의 일을 1시간하여 0으로 만들면 5 * 5 + 8 * 8 + 0 * 0이 야근 지수가 되며 이 값은 89가 됩니다.

정리 해보면 모든 일의 제곱의 합이 최소가 되려면 가장 큰 일의 지수를 낮추어 나가야 합니다.

 

여기서 추가로 생각해야 하는 부분은 1시간씩 일을 진행하다 보면 가장 많이 남은 일이 변경 될 수 있다는 것 입니다.

 

이번에는 Works가 [7, 6]이고 N이 3인 경우

1. 7을 6으로 만들고 나면 N은 2가 남고 Works는 [6, 6]이 됩니다.
   
   
2. 7에서 6이된 일을 1시간 더 일하면 N은 1이 남고 Works는 [5, 6]이 됩니다.
   
   
3. 7에서 시작한 일이 2시간 일을 진행하여 5가되어 가장 큰 일의 지수가 아니므로 이번에는 6의 일을 1시간 일하면
   N은 0이 되고 Works는 [5, 5]가 됩니다.
   
   
4. N이 0이라는 것은 일을 할 수 있는 시간을 모두 일하였다는 것으로 Works에 남은 일들의 제곱의 합인 50이 야근지수가 됩니다.

위 예시로 1시간씩 일을 진행하다 보면 가장 많이 남은 일이 변경이 될 수 있다는 것을 확인 하였습니다.

 

위 과정들에서 본 것을 적용하기 가장 좋은 자료구조는 우선순위 큐로 항상 Collection의 가장 큰값 또는 가장 작은 값을 가져올 수 있으므로 우선순위 큐를 이용하여 코드를 작성 하였습니다.

 

for (int work : works) queue.offer(work);

입력으로 주어진 Works를 우선순위 큐에 추가 합니다.

 

for (int i = 0; i < n; i++) {
	int work = queue.poll();

	if (work == 0)
		break;
	else
		queue.offer(work - 1);
}

이후 입력으로 주어진 N만큼 반복을 통해 큐에 입력된 일들 중 가장 큰 값에 -1을 진행 합니다. 위 과정을 통해 가장 큰 일을 1시간씩 수행하는 것을 코드화 하였습니다.

※ 단 큐에서 가장 큰 일이 0이 된다는 것은 모든 일을 다 끝내어 야근을 할 필요가 없으므로 break를 통해 반복문을 종료 합니다.

 

long answer = 0;
for (int sub : queue) answer += Math.pow(sub, 2);

return answer;

마지막으로 큐에 남은 모든 일들의 제곱의 값 더하여 반환하여 문제를 해결 하였습니다.

 

5. 코드

전체 코드는 Git에 있습니다.

PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
for (int work : works) queue.offer(work);

for (int i = 0; i < n; i++) {
	int work = queue.poll();

	if (work == 0)
		break;
	else
		queue.offer(work - 1);
}

long answer = 0;
for (int sub : queue) answer += Math.pow(sub, 2);

return answer;