야근지수 (level3)

이번 문제에 문제 푸는 방식을 생각해내는 것에서는 어렵지 않았습니다.

 

문제를 푸는 방식은 배열에서 가장 큰 수를 매번 고르고, 거기서 1을 빼는 식으로 n이 0이 될때까지 진행하는 방식입니다.

 

다만, 처음 풀때는 배열을 이용하여 내림차순으로 정렬 후, 가장 큰수에서 1을 빼고, 다시 배열을 재정렬 해주는 방식으로 구현했습니다.

이렇게 하니 결과는 맞으나, 실행시간 테스트에서 실패가 발생했습니다.

 

딱봐도 매번 재정렬하는 부분이 문제라 생각되어, 우선순위 큐를 이용하여 정렬이 되게끔 하면, 더 빠르 실행속도를 낼 수 있다 판단하였고, 그리하여 구현을 통해 테스트를 모두 통과할 수 있었습니다.

 

우선순위 관련된 문제가 나올때는 우선순위 큐나, treemap을 이용하면, 정렬에 있어서 더 좋은 효과가 난다고 생각합니다.

 

import java.util.*;

class Solution {
	public long solution(int n, int[] works) {
		long answer = 0;

		// 내림차순으로 우선순위큐 생성
		PriorityQueue<Integer> q = new PriorityQueue<Integer>(Collections.reverseOrder());
		for (int w : works) {
			q.offer(w);
		}

		int tmp = -1;
		for (int i = 0; i < n; i++) { // 횟수만큼
			tmp = q.remove(); //꺼내서
			if (tmp > 0)
				tmp--; // 빼기
			
			q.offer(tmp); // 다시 넣기 (우선순위큐에 넣음으로써, 자동 정렬됨.)
		}

		for (int a : q) { // 제곱해서 누적합 구하기
			answer += a * a;
		}

		return answer;
	}
}