[프로그래머스] 야근 지수

야근 지수(https://programmers.co.kr/learn/courses/30/lessons/12927)

---

1. 이해하기

• N시간 동안 야근 피로도를 최소화하도록 일하려고 한다. Demi는 1시간 동안 작업량 1만큼을 처리할 수 있다고 한다.
• n의 범위와 works의 배열의 길이가 크기 때문에 일반적으로 해서는 시간초과가 나게 된다.
• heap혹은 binary_search를 이용해서 최댓값을 찾는다. 최댓값을 찾는 이유는 큰 값일수록 제곱의 값이 커지기 때문이다.

---

2. 구현하기

• 만약 works에 있는 양이 n값보다 작으면 0을 리턴해준다. 시간안에 모든 일을 처리할 수 있고 야근을 하지 않아도 되는 상황이기 때문이다.

• heap에 works의 값들을 넣어준다. 이후 n이 0이 될 때까지 최댓값을 찾아서 -1해준다.

  • python에서는 기본으로 min_heap이 되는듯하다. 따라서 값들을 음수로 만든 후 넣어준다.

    import heapq
    
    def solution(n, works):
        answer = 0
        if sum(works) < n: return 0
        heap = []
        for work in works:
            heapq.heappush(heap,-work)
        while n > 0:
            maxWork = -heapq.heappop(heap)
            maxWork-=1
            heapq.heappush(heap,-maxWork)
            n-=1
        for work in heap:
            answer += work**2
        return answer

  • c++에서는 최대힙이 기본인듯 하다.

    #include <string>
    #include <vector>
    #include <queue>
    
    using namespace std;
    
    long long solution(int n, vector<int> works) {
        long long answer = 0;
        int sum = 0;
        for(int work: works)
            sum += work;
        if(sum-n <= 0) return 0;
        priority_queue<int> pq;
        for(int work: works)
            pq.push(work);
        while(n > 0) {
            int maxVal = pq.top();
            pq.pop();
            maxVal--;
            pq.push(maxVal);
            n--;
        }
        while(!pq.empty()) {
            answer += pq.top()*pq.top();
            pq.pop();
        }
        return answer;
    }

---

3. 배운점

• python에서 heap을 사용하기 위해서는 import heapq을 해줘야한다.
  • 일반 리스트를 만들어서 값을 넣어줄 때는 heapq.heappush(리스트,값)
  • 값을 뺄때는 heapq.heappop(리스트)