lv3 야근 지수

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

import java.util.*;
import java.lang.Math;
class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
        for(int i=0; i<works.length; i++) {
            q.add(works[i]);
        }
        while(n!=0) {
            int val = q.poll();

            if(val <= 0) {
                return 0;
            }
            n--;
            q.add(val-1);
        }
        while(q.peek()!=null) {
            answer +=(long) Math.pow(q.poll(), 2);
        }
        return answer;
    }
}

처음에 풀 때는 파이썬으로

#효율성 테스트 실패
def solution(n, works):
	answer = 0
	summation = sum(works)
	summation = summation - n
	if summation < 0:
  	  return 0

	while(n!=0):
   		works[findMax(works)] -= 1
	    n -= 1

	for i in works:
    	answer += i**2
	return answer
    
def findMax(works):
	maxVal = max(works)
	for j in range(len(works)):
		if works[j]==maxVal:
		return j

위와 같이 풀었는데 O(n^2) 시간복잡도를 갖아서 그런가 효율성 테스트에서 계속 실패했다.

그래서 아직 파이썬에서 자료구조 클래스를 따로 공부해 놓지 않아서 Java로 Priority Queue를 사용해서 풀었더니 다행히 통과 했다.
Priority Queue로 푼 코드의 시간복잡도는 O(max(n, m) * log m)이다. (m은 works의 length)

TODO: python pq 공부하기
21. 12. 23
https://velog.io/@iknow/priority-queue

17. 12. 23: python3 PriorityQueue를 사용한 풀이

from queue import PriorityQueue
def solution(n, works):
   
    q = PriorityQueue()
   
    for i in works:
        q.put((-i, i))
    while n!=0:
        n -= 1
        work = q.get()[1] - 1
        if work < 0:
            return 0
        q.put((-work, work))
       
    answer = 0
    while not q.empty():
        work = q.get()[1]
        answer += work**2
    return answer

시간복잡도가 $O(nlog n)$으로 판단되는데 효율성 테스트에서 실패했다.
파이썬 성능으로 인한 시간 부족인지, 다른 더 효율적인 알고리즘이 있는지 확인이 필요하다.

17.12.23: heapq를 이용한 풀이

import heapq
def solution(n, works):
   
    heap = []
   
    for i in works:
        heapq.heappush(heap, -i)
    while n!=0:
        n -= 1
        work = -heapq.heappop(heap) -1
        if work < 0:
            return 0
        heapq.heappush(heap, -work)
    answer = 0
    while not len(heap)==0:
        work = heapq.heappop(heap)

        answer += work**2
    return answer

heapq를 사용하면 더 빠르게 사용할 수 있다는 정보를 읽고 heapq를 이용한 풀이를 작성해봤다.
이 코드의 시간복잡도 또한 $O(nlogn)$인데, 이 풀이는 통과하는 것을 보면 파이썬 성능의 문제를 여기서 겪은 것 같다.

TODO: heapq 공부하기