[알고리즘] 프로그래머스 야근 지수 :: 우유

https://school.programmers.co.kr/learn/courses/30/lessons/12927

프로그래머스

코드 설명

우선순위큐의 개념만 이해하고 있다면 어렵지 않은 문제였었다. 

Priority Queue

PriorityQueue란 우선순위 큐로써 일반적인 큐의 구조 FIFO(First In First Out)를 가지면서, 데이터가 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 데이터가 먼저 나가는 자료구조이다.

PriorityQueue를 사용하기 위해선 우선순위 큐에 저장할 객체는 필수적으로 Comparable Interface를 구현해야한다.

Comparable Interface를 구현하면 compareTo method를 override 하게 되고 해당 객체에서 처리할 우선순위 조건을 리턴해주면 PriorityQueue 가 알아서 우선순위가 높은 객체를 추출 해준다.

PriorityQueue는 Heap을 이용하여 구현하는 것이 일반적이다.

데이터를 삽입할 때 우선순위를 기준으로 최대 힙 혹은 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아 옮기는 방식으로 진행된다.
최대 값이 우선순위인 큐 = 최대 힙, 최소 값이 우선순위인 큐 = 최소 힙

남은 작업량들의 제곱의 합이 야근 지수기 때문에 가장 높은 야근 지수를 N 시간 만큼 -1 해주면 된다.
우선순위큐는 내부적으로 Queue에서 우선순위가 높은 데이터가 먼저 나가기 때문에 poll 할때마다 가장 높은 데이터가 가장 높은 우선순위로 옮겨진다. 이러한 특징을 이용하여 풀면 아래 코드와 같이 구현할 수 있다.

전체 코드

import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {

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

        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
        for (int work : works) {
            pq.add(work);
        }

        while (n > 0) {
            int max = pq.poll();
            pq.add(--max);
            n--;

            if(pq.peek() == 0 && n > 0) break;
        }

        for (Integer num : pq) {
            answer += Math.pow(num, 2);
        }
        
        if(n != 0) answer = 0;

        return answer;
    }
}