[프로그래머스] Java : 야근 지수(우선순위 큐)

 

 

 

---

 

이번 문제는 우선순위 큐를 사용하는게 포인트입니다.

큐는 선입선출(FIFO)을 특징으로 갖는 자료구조입니다.

우선순위 큐는 먼저 들어온 데이터가 아닌, 우선순위가 높은 데이터가 먼저 나가는 자료구조입니다.

 

0. 선언

// 우선순위 오름차순
Queue<Integer> q = new PriorityQueue<>();

// 우선순위 내림차순
Queue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());

 

1. 기본 메서드

add(E e)	큐에 데이터를 넣을 때 사용 만약 큐가 가득 차면, IllegalStateException 발생
offer(E e)	큐에 데이터를 넣을 때 사용 데이터를 넣지 못할 때는, false를 반환
poll()	첫 번째 값을 반환하고 제거 큐가 비어있으면 null 반환
remove()	첫 번째 값을 반환하고 제거 큐가 비어있으면 NoSuchElementException 발생
peek()	첫 번째 값을 반환 큐가 비어있으면 null 반환
isEmpty()	큐에 데이터가 없으면 true 아니면 false 반환
size()	큐에 데이터가 몇 개나 있는지 반환

 

 

---

 

 

각각의 작업량을 제곱해서 전부 더한 값이 최소가 되려면,
제일 양이 많은 작업을 쳐내면서 야근하면 됩니다.

예) [5, 4, 1] -> [4, 4, 1] -> [3, 4, 1] -> [3, 3, 1]

우선순위 큐는 데이터를 삽입할 때마다 우선순위를 재배치합니다.

 

그러므로
첫 번째 데이터를 뽑아 -1 하고 삽입 -> (알아서 재배치) -> 첫 번째 데이터를 뽑아 -1 하고 삽입 -> (알아서 재배치) ... 
하는 과정을 남은 퇴근까지 반복해주면 됩니다.

 

1. 우선순위 큐 구현 및 데이터 적재

Queue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
for (int w : works) {
    q.add(w);
}

 

2. 첫 번째 데이터를 뽑아 -1 하고 삽입

for (int i = 0; i < n; i++) {
    int work = q.poll() - 1;
    q.add(work < 0 ? 0 : work);
}

 

3. 남은 작업량 제곱해서 더한 값 구하기

for (int i : q) {
    answer += (long) Math.pow(i, 2);
}

return answer;

 

 

---

 

 

 

import java.util.*;

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

        Queue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
        for (int w : works) {
            q.add(w);
        }

        for (int i = 0; i < n; i++) {
            int work = q.poll() - 1;
            q.add(work < 0 ? 0 : work);
        }

        for (int i : q) {
            answer += (long) Math.pow(i, 2);
        }

        return answer;
    }
}