야근 지수
Last update: a year ago by nowwaterReading time: 2 min
문제
코드
코드 보기
package programmers.question;import java.util.Comparator;import java.util.PriorityQueue;public class Q12927 {public static long solution(int n, int[] works) {long answer = 0;PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());for (int work : works) {pq.add(work);}for (int i = 0; i < n; i++) {int res = pq.poll() - 1;if(res < 0) return 0;pq.add(res);}while (!pq.isEmpty()) {int top = pq.poll();answer += top * top;}return answer;}public static void main(String[] args) {int n1 = 4, n2 = 1, n3 = 3;int [] works1 = {4, 3, 3}, works2 = {2, 1, 2}, works3 = {1, 1};System.out.println(solution(n1, works1));System.out.println(solution(n2, works2));System.out.println(solution(n3, works3));}}
⭐️느낀점⭐️
처음 떠올린 방법대로하면 시간 초과가 날 것이라고 예상하고 다른 효율적인 방법을 생각해보다가, 그 방법이 너무 명확해서 제출해보니 통과했다.
계산해봤을 때 너무 터무니없는 시간이면 다시 생각해보고, 그게 아니라면 제출해보고 더 효율적인 방법을 생각해봐야겠다.
풀이 📣
1️⃣ 모든 작업량을 Max Heap에 저장한다.
2️⃣ 작업량이 많은 작업순으로 하나씩 작업을 처리한다.
- 그리디하게 생각했을 때, 야근 지수를 구하려면 최종적으로 남은 작업량의 제곱의 값들을 더하기 때문에 가장 많이 남은 작업을 조금이라도 줄여야 최종 결과가 더 줄어든다.- 즉, 더 적은 작업량을 줄여서 제곱하는 것보다 더 큰 작업량을 줄여서 제곱하는 것이 훨씬 더 유리하다.- max heap 에서 하나씩 꺼내서 1 만큼의 작업을 처리하고 다시 삽입해준다.
3️⃣ N 만큼 처리한 후, Max Heap에 남아 있는 모든 작업들을 꺼내서 야근지수를 구해 출력한다.
실수 😅
O(N Len(works) log(Len(works))) => O(1000,000 20,000 lg(20,000)) 이라고 생각해서 당연히 어마어마한 시간이 걸릴 것이라 생각했다..
하지만 생각해보니 O(N * log(Len(works))) 만 있으면 해결이 된다. 단순히 삽입/삭제만 일어나기 때문이다!!
그럴 경우의 시간복잡도는 O(1000,000 * log(20,000)) 이지만
우선순위큐 삽입/삭제라는 비교적 단순한 작업을 수행하기 때문에 대략 1초 내에 동작한다.