오늘은 프로그래머스의 야근지수라는 문제를 풀어 보았다.
문제 설명은 다음과 같다.
문제 설명
회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다.Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요.
제한 사항
- works는 길이 1 이상, 20,000 이하인 배열입니다.
- works의 원소는 50000 이하인 자연수입니다.
- n은 1,000,000 이하인 자연수입니다.
이 문제는 회사원이 야근까지 남은 시간 n과 각각 작업에 걸리는 시간인 works를 사용하여 가장 작은 피로도를 구하는 문제이다.
처음에는 내림차순으로 배열을 정렬 후 가장 큰 값에서 작은 값을 빼는 순서로 하려고 했다.
근데 생각을 해보니 [4, 3, 3]에서 n이 4일 때 4를 제거하면 3의 제곱 두개를 더한 것이 값으로 나올텐데 정답은 4에서 2를 빼고 3에서 각각 1을 빼서 제곱해서 더해준 12라는 값이 정답이다.
그래서 이 풀이는 정답이 아니라고 생각하고 다음 방법을 생각해 보았다.
다음 풀이는 내림차순으로 정렬이 된 배열에서 순서대로 사이클을 돌며서 1씩 빼주는 방법을 생각해 보았다.
이 방법으로 풀어보니 테스트 케이스는 전부 정답이 나왔지만 제출에서 많은 오답이 나와서 이 풀이도 정답이 아니라고 생각하고 다른 방법을 생각해 보았다.
여기서 문득 든 생각이 가장 큰 값이 제곱을 하였을 때 늘어나는 값의 비중이 가장 높으니 가장 큰 값을 줄여주는 것이 맞긴 한데 값을 줄일 때마다 가장 큰 값이 바뀐다는 것이다.
그래서 생각한 방법이 값을 줄이고나서 가장 큰 값을 다시 골라주어 그 값을 줄이고 이 것을 반복하는 방법이다.
정답 코드는 다음과 같다.
import java.util.*;
class Solution {
public long solution(int n, int[] works) {
long answer = 0;
PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
for (int i = 0; i < works.length; i++) {
queue.add(works[i]);
}
for (int i = 0; i < n; i++) {
int value = queue.poll();
if (value > 0) {
value--;
}
queue.add(value);
}
while(!queue.isEmpty()) {
answer += Math.pow(queue.poll(), 2);
}
return answer;
}
}여기서는 PriorityQueue를 사용하여 값을 넣을 때마다 정렬이 되게 하였다.
값을 꺼낼 때 가장 큰 값을 꺼내기 위해 우선순위 큐를 내림차순으로 선언했다.
우선 모든 작업시간들을 우선순위 큐에 하나씩 집어넣는다.
이렇게 하면 값을 하나씩 넣을 때마다 내림차순으로 정렬이 될 것이다.
그리고 큐에서 값을 하나씩 꺼낼 때마다 그 값에서 1씩 빼주고 다시 큐에 삽입하는 과정을 n만큼 반복한다.
이 반복문에서 한가지 조건이 있는데 꺼낸 작업의 시간이 0일때는 값을 빼주지 않고 다시 넣는다 남은 작업시간이 음수가 될수 없기 때문이다.
반복문이 종료된 후 큐에 존재하는 모든 값을 제곱해서 더해주면 정답이 되게 된다.
큐(Queue)의 개념
큐(Queue)는 스택(Stack)과 다르게 먼저 들어온 것이 먼저 나가는 "선입선출"로, FIFO(First In First Out)의 구조를 가지고 있다.
삭제 연산이 수행되는 곳을 프론트(front), 삽입 연산이 이루어지는 곳은 리어(rear)로, FIFO 구조를 위해서 스택과 다르게 큐의 한쪽 끝에는 삽입 작업이, 다른 한쪽 끝에서는 삭제 작업이 나뉘어서 이루어지고 있다.
큐는 리어(rear)에서 이루어지는 삽입 연산을 인큐(Enqueue)라고 부르며, 프론트(Front)에서 이루어지는 삭제 연산을 디큐(Dequeue)라고 부른다.
우선순위 큐(Priority Queue)의 개념
PriorityQueue란 우선순위 큐로써 일반적인 큐의 구조 FIFO(First In First Out)를 가지면서, 데이터가 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 데이터가 먼저 나가는 자료구조이다.
PriorityQueue를 사용하기 위해선 우선순위 큐에 저장할 객체는 필수적으로 Comparable Interface를 구현해야한다.
Comparable Interface를 구현하면 compareTo 메서드를 override 하게 되고 해당 객체에서 처리할 우선순위 조건을 리턴해주면 PriorityQueue가 알아서 우선순위가 높은 객체를 추출 해준다.
PriorityQueue는 Heap을 이용하여 구현하는 것이 일반적이다.
데이터를 삽입할 때 우선순위를 기준으로 최대 힙 혹은 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아 옮기는 방식으로 진행된다.
최대 값이 우선순위인 큐 = 최대 힙, 최소 값이 우선순위인 큐 = 최소 힙
