[ 알고리즘 ] 코딩 - Programmers - 야근지수.java

---

문제 링크

programmers.co.kr/learn/courses/30/lessons/12927

코딩테스트 연습 - 야근 지수

---

문제 개요

프로그래머스 - Level 3 - (자바)야근지수 - 우선순위큐(PriorityQueue)를 이용한 최대값 갱신

제한사항

입출력예시

Demi 씨가 1시간에 1만큼의 일을 함.

야근 피로도 = 각기 남은 일들의 제곱들의 합

 

---

로직

* 남은 일이 제곱이 되기 때문에 가장 큰 수를 찾아내서 점점 작게 만들어 줘야한다

Step 01. 입력들을 정렬해줄 PriorityQueue를 하나 준비한다. 이때 PQ는 내림차순으로 정렬 할 것이다

Step 02. 내림차순이기 때문에 PQ 가장 앞 원소가 입력의 가장 큰 값이다. 이 값을 -1 해준다음 PQ에 다시 offer한다.

Step 02-1. PQ의 특성으로인해 내림차순 재정렬한다.

Step03. n번의 횟수만큼 반복한다. 이때 최대 값이 0인 경우에는 야근을 하지 않아도 되는 경우이므로 0을 리턴해준다.

Step 04. PQ안에 있는 숫자들을 제곱해서 더하면 정답!

---

코드

import java.util.PriorityQueue;
class Solution {
		public long solution(int n, int[] works) {
			// 내림차순 정렬
			PriorityQueue<Integer> pQueue = new PriorityQueue<Integer>(
            						(o1, o2) -> o2.compareTo(o1));
			int length = works.length;
			for (int i = 0; i < length; i++) {
				pQueue.offer(works[i]);
			}
			
			// 최대값을 점점 줄여나감
			for (int i = 0; i < n; i++) {
				int max = pQueue.poll();
				if (max == 0) // 야근 없음!
					return 0;
				pQueue.offer(--max);
			}

			long answer = 0;
			int size = pQueue.size();
			// PQ에 저장된 값의 제곱들의 합이 정답
			for (int i = 0; i < size; i++) {
				int num = pQueue.poll();
				answer += Math.pow(num, 2);
			}
			return answer;
		}
	}