[프로그래머스] 야근 지수 (JAVA)

문제 출처 - Programmers

문제는 여기

프로그래머스

---

[풀이]

1. 내림차순의 우선순위큐를 생성한다

2. 큐에 값을 넣어준다.

3. 큐에서 값을 빼주고 해당 값이 0보다 작으면 더 탐색할 필요가 없으므로 탈출, 아니라면 가장 큰 값에서 1을 뺀 값을 큐에 넣어준다.

4. 큐가 빌때까지 값을 제곱해서 더해준다.

5. 결과를 출력한다.

[접근]

1. 배열로 문제를 풀면 되겠다고 생각하였는데 효율성에서 떨어져 우선순위큐로 문제를 해결하였다.

[코드]

import java.util.PriorityQueue;
import java.util.Collections;

class Solution {
    public long solution(int n, int[] works) {
        // 큰 거부터 내림차순으로 정렬되게 생성
        PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());

        // 큐에 값 넣기
        for (int i = 0; i < works.length; i++) {
            q.offer(works[i]);
        }
        
        for (int i = 0; i < n; i++) {
            // 큐에서 값 빼기
            int max = q.poll();
            // 가장 큰 값이 0보다 작으면 더 탐색 필요없음
            if (max <= 0)
                break;
            // 아니라면 큐에서 젤 큰 값에서 1 빼주기
            q.offer(max - 1);
        }
        
        long tired = 0;
        // 큐가 빌 때까지
        while (!q.isEmpty()) {
            int k = q.poll();
            // 남은 작업의 제곱을 더하기
            tired += k * k; 
        }
        
        return tired;
    }    
}