[프로그래머스]연습문제 : 야근 지수 (level 3) (c++)

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

코딩테스트 연습 - 야근 지수

 

 

#include <string>
#include <vector>
#include <queue>

using namespace std;

long long solution(int n, vector<int> works) {

    // 우선 순위 큐에 works 요소 복사
    priority_queue<int, vector<int>, less<int>> pq;
    int sum = 0;
    for (int i : works)
    {
        pq.push(i);
        sum += i;
    }

    // 전체 남은 작업량보다 n이 같거나 크다면 0 반환
    if (sum <= n)
    {
        return 0;
    }

    // n시간 동안 가장 큰 작업물을 1씩 처리
    while (n--)
    {
        int tmp = pq.top();
        pq.pop();
        pq.push(tmp - 1);
    }

    // 야근 피로도 계산
    long long answer = 0;
    while (!pq.empty())
    {
        answer += (long long)pq.top() * pq.top();
        pq.pop();
    }

    return answer;
}

 

 

우선순위 큐를 활용하는 문제였다.

전체 남은 작업량보다 n이 같거나 클 경우에는 남은 작업물이 없으므로 야근피로도가 0이다.

이점을 처리 해주면 효율성 체크 속도가 증가한다.

 

n은 1,000,000 이하인 자연수

반복문을 n크기만큼 돌리지만, n의 크기가 100만으로 그리 크지 않으므로 가능하다.