코딩테스트 -- 야근 지수 - (프로그래머스 / C++)

프로그래머스

 

문제!

---

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

 

---

요약하면 여러가지 일들이 있고 총할수있는 일  n을 적절히 배분하여 야근지수(제곱의 합)의 최소값을 찾는 문제입니다!

 

이문제에서  저는 작업들의 길이가 2만 밖에 되지 않기에

최댓값에서 1씩 작업을 처리시켜 야근 지수를 최소화 시키는 방법을 사용해 보기로 했습니다.

 

 

시작!

 

먼저 작업들을 거꾸로 정렬 해줍시다

sort(works.rbegin(),works.rend());

 

 

다음은 맨 앞의 값에서 1씩 제거해주며 다시 정렬시키는 작업을 반복하여 n을 처리해줍시다.

while(n>0){
        if(works[0]>0){// 1씩 빼주면서 재정렬
            works[0]-=1;
            n--;
            check1=true;
            sort(works.rbegin(),works.rend());
        }
        else{// 다 비워버림
            check1=false;// 전부 비워졌는지를 체크
            break;
        }
    }

 

이제 모든 works가 0이 아닌지를 판별후 계산해줍시다!

if(check1){
        for(int i : works){
            answer+=i*i;
        }
    }

 

여기까지 했을때 어딘가 불안하지 않나요..?

 

 

위의 코드대로 했을때 정확성은 완벽합니다!

하지만... 매번 sort연산을 하는 부분에서 약간 무거워져 효율성에서는 실패....

 

 

 

 

 

이부분을 해결하기 위해 모든 작업들을 우선순위 큐에 넣어서 관리하는 방법이 있었습니다....

우선 순위 큐를 사용하지 않고 해볼려고 했지만 먼가 더 엉켜버려서 포기해버렸습니다(다음에 다시!)

 

priority_queue<int> pq(works.begin(), works.end());

 

나머지 풀이 구조는 똑같은데

우선순위 큐를 사용함으로써 매번 sort연산을 해주지 않는것이  이번 문제의 해결책이였던것 같습니다!

 

끝!

 

 ALL

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

using namespace std;

long long solution(int n, vector<int> works) {  
    
    priority_queue<int> pq(works.begin(), works.end());
    long long answer = 0;
    
    while(n > 0){// 작업 시작!
        if(pq.top() > 0){ 
            int temp = pq.top();
            pq.pop();
            pq.push(temp-1);
            n--;
        }
        else{// 모든 작업 클리어
            break;
        }
    }
    
    
    while(!pq.empty()){// 모든작업 출력
        long long memo = pq.top();
        pq.pop();
        answer += (memo*memo);
    }  
    return answer;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!