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

---

운동은 "적절한 강도의 꾸준함"과

간혹 컨디션이 좋을 때
"근육통을 유발하는 강도"로 운동을 하면

근육 생성 및 유지에 효과가 좋다고 합니다.

 

뇌 운동도 비슷하다고 생각합니다.

매일 매일 어려운 문제를 풀다가 빠르게 지쳐 손을 놓기보다는

쉬운 문제를 매일 매일 풀어보는 습관을 들이고자 하는 데에 목적이 있는

"심심풀이땅콩코테"입니다.

 

간혹 이상한 방법으로 문제를 풀긴 합니다(정말 '어우 이게머야..' 할 정도)

그냥 참고만 해주세요 :)

 

(덧글로 본인의 풀이 방법을 적어주신다거나(본인의 코드를 자랑해주세요)

평화적인 지적을 환영합니다.)

---

 

 

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

using namespace std;

long long solution(int n, vector<int> works) {
    long long answer = 0;
    
	int totalWork = 0;
	for (auto& w : works)
	{
		totalWork += w;
	}
    
    // 야근없음!
    if (n >= totalWork) return 0;
    
	// 우선순위 큐
	priority_queue <int> q;
	for (auto& w : works)
	{
		q.push(w);
	}

	int count = n;
	while (count > 0)
	{
		int t = q.top();
		q.pop();
		q.push(t - 1);

		count--;
	}
    
	// 남은 일로 야근 피로도 계산
	while (!q.empty())
	{
		answer += q.top() * q.top();
		q.pop();
	}
    
    return answer;
}

 

• priority_queue 우선순위 큐 : Queue의 한 종류. 우선순위에 따라 정렬된 Queue 로, 기본적으로 내림차순이다. 원소가 삽입되면(Push) 우선순위에 맞춰 queue가 정렬된다. 삭제(Pop)은 정렬된 Queue의 앞에서 먼저 실행된다. 자료구조 Heap으로 구현된 것으로, 어떤 원소를 삽입(Push)해서 생기는 정렬과정은 O(logN) 만에 이루어진다.

 

이 문제의 핵심은 vector 리스트 안의 남은 일의 양이 서로 비슷해야 한다는 것이다. 처음엔 그걸 간과하고 그냥 모든 원소들을 1씩 삭제했다가 틀렸었고, 최대한 야근 피로도를 줄이기 위해 가장 큰 일 먼저 줄여나가야한다는 것을 알았다. 그렇기에 가장 큰 원소들을 먼저 1씩 줄여, 각각의 원소들의 크기가 비슷해지도록 해야한다.