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

< 해설 >

works 벡터에 들어있는 값을 최대한 균등하게 만들어 주는 것이 포인트인 문제이다.

어제 푼 문제와 비슷하게 n이 works.size() 보다 더 클 경우에 벡터의 모든 요소에 n/size 한 몫만큼을 빼주었는데 문제가 생긴다. 질문하기에 있는 반례는 다음과 같다.

위의 상황에서는 내가 생각한 접근법이 맞지 않는다... 무조건 가장 큰 원소에 접근해서 값을 빼주고 싶은데 말이다.

 

그래서 생각해 낸 방식이 우선순위 큐를 이용한 방식이다. 무식하게 우선순위 큐를 만들고 큐의 top에 접근해서 하나씩 빼주고 0이 아니면 다시 넣어주었다. 이렇게 하면 문제를 쉽게 풀 수 있다. n이 1,000,000 이 최대 값이라 걱정을 했으나,, 어짜피 n은 한번만 돌면 되므로 그냥 써도 시간문제는 생기지 않는다.

 

< 문제 >

회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다.Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요.

 

 

< 풀이 >

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

using namespace std;

long long solution(int n, vector<int> works) {
    long long answer = 0;
    priority_queue<int> que;
    
    for(int w : works)
        que.push(w);
    
    while(!que.empty() && n>0)
    {
        int curQue = que.top();
        que.pop();
        curQue--;
        if(curQue != 0)
            que.push(curQue);
        n--;
    }
    
    while(!que.empty())
    {
        answer += que.top()*que.top();
        que.pop();
    }
    
    return answer;
}

효율성 테스트도 나쁘지 않다!