프로그래머스, 야근 지수
문제 설명
Demi는 야근을 하면 야근 피로도가 쌓인다. 야근 피로도는 남은 작업시간 제곱의 합이며 1시간 야근을 하면 작업량을 1만큼 처리할 수 있다. 이때 야근 피로도는 남은 야근 작업량의 제곱의 합이다. n을 모두 사용할 때 최소의 야근 작업량을 구하시오.
https://school.programmers.co.kr/learn/courses/30/lessons/12927?language=java
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 풀이
첫 번째 접근
첫 번째 예를 한 번 보자. n이 4이고 작업량이 [4, 3, 3]일 때 야근을 하고 난 결과는 [2, 2, 2]이다. 또 두 번째 예를 보면 [2, 1, 2]에서 야근을 하고 나면 [1, 1, 2]가 된다.
최초 값과 그 결과를 비교하면 작업량이 큰 수대로 빠지는 것을 알 수 있다. 그러므로 우선순위 큐를 이용해서 제일 큰 숫자가 먼저 나오도록 하면 원하는 결과를 얻을 수 있다.
일단 우선순위 큐를 내림차순으로 선언하고 넣어준다.
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for(int i=0; i<works.length; i++){
pq.add(works[i]);
}
그리고 while문을 돌려주면서 제일 큰 수에 하나 빼주고 n 또한 하나 빼준다. 그리고 큐에서 빼준 수를 다시 넣어줘야 하는데, 만일 그 수가 0이라면 넣지 않는다.
여기서 탈출문은 우선순위 큐가 0이거나 n이 0일 때다.
while(true){
if(pq.size() == 0 || n == 0){
break;
}
int current = pq.poll();
current--;
n--;
if(current == 0){
continue;
}
pq.add(current);
}
우선순위 큐가 0이면 0을 반환한다. 0이 아니면 숫자를 큐에서 하나씩 빼서 제곱을 한 후 answer에 더해준다.
if(pq.size() == 0){
return 0;
}
while(pq.size() != 0){
answer += (Math.pow(pq.poll(), 2));
}
코드
java
import java.util.*;
class Solution {
public long solution(int n, int[] works) {
long answer = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for(int i=0; i<works.length; i++){
pq.add(works[i]);
}
while(true){
if(pq.size() == 0 || n == 0){
break;
}
int current = pq.poll();
current--;
n--;
if(current == 0){
continue;
}
pq.add(current);
}
if(pq.size() == 0){
return 0;
}
while(pq.size() != 0){
answer += (Math.pow(pq.poll(), 2));
}
return answer;
}
}