프로그래머스: 야근 지수⭐⭐⭐

난이도 ⭐⭐⭐
유형 : 자료, 구현

🧐 문제

문제 설명

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

제한 사항

• works는 길이 1 이상, 20,000 이하인 배열입니다.
• works의 원소는 50000 이하인 자연수입니다.
• n은 1,000,000 이하인 자연수입니다.

입출력 예

works	n	result
[4, 3, 3]	4	12
[2, 1, 2]	1	6
[1,1]	3	0

---

입출력 예 설명

접기/펼치기

**입출력 예 #1**

n=4 일 때, 남은 일의 작업량이 [4, 3, 3] 이라면 야근 지수를 최소화하기 위해 4시간동안 일을 한 결과는 [2, 2, 2]입니다. 이 때 야근 지수는 22 + 22 + 22 = 12 입니다.

**입출력 예 #2**

n=1일 때, 남은 일의 작업량이 [2,1,2]라면 야근 지수를 최소화하기 위해 1시간동안 일을 한 결과는 [1,1,2]입니다. 야근지수는 12 + 12 + 22 = 6입니다.

**입출력 예 #3**

남은 작업량이 없으므로 피로도는 0입니다.

---

🔍 힌트

이번 문제는 이전에 풀었던 최고의 집합 문제와 매우 비슷하다.

해당 문제와 비슷하게 배열 속 숫자들의 편차를 최대한 줄이는 방향으로 가야, 제곱 합을 최소로 만들 수 있다.

n	works
n=5	works=[4,2,2]

예를 들어 위와 같은 상황이라 생각해보자.
[3,0,0], 결과 9로 만드는 것보단,
[1,1,1], 결과 3으로 만드는 것이 최소화된다.

이렇게 나오는 이유는 이차함수 그래프를 생각해보면 쉽게 알 수 있다.
그러므로, 배열 속 숫자들의 편차를 줄이는 것이 해결 방법이다.

이제 ‘2중 for문으로 구성된 벡터(배열)’ 혹은 ‘우선순위 큐’를 사용하여 풀면 된다.

---

✏️ 나의 풀이(우선순위 큐)

#include <bits/stdc++.h>

using namespace std;

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

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

    while(n!=0) {
        int t = pq.top();
        if(t == 0) return 0;
        pq.pop();
        pq.emplace(t-1);
        n--;
    }

    long long result = 0;
    while(!pq.empty()) {
        int t = pq.top();
        pq.pop();
        result += (long long)t*t;
    }
    return result;
}

✏️ 나의 풀이(벡터)

#include <bits/stdc++.h>

using namespace std;

long long solution(int n, vector<int> works) {
    // 벡터 내림차순 정렬. 한번만 해주면 됨
    sort(works.begin(), works.end(), greater<int>());
    
    for(int i=0; i<n; i++) {
        for(int j=0; j<works.size()-1; j++) {
            if(works[j] > works[j+1]) {
                works[j] = works[j]-1;
                break;
            }
            // 배열의 끝에 도달했다는 것은,
            // 모든 숫자들이 같은 상태. 우측의 값을 1 줄인다.
            if(j == works.size()-2 && i < n-1) {
                // 모든 피로도가 0인 경우
                if(works[works.size()-1] == 0) return 0;
                works[works.size()-1] -= 1;
            }
        }
    }

    long long result = 0;
    for(auto work : works) {
        result += (long long)work*work;
    }
    
    return result;
}

✔️ 다른 사람의 풀이

// 문제가 개편되었습니다. 이로 인해 함수 구성이나 테스트케이스가 변경되어, 과거의 코드는 동작하지 않을 수 있습니다.
#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;

int noOvertime(int no, vector<int> works)
{
    int answer = 0;

    while (no != 0)
    {
        *max_element(works.begin(), works.end()) -= 1;
        no -= 1;

    }
    for (int i = 0; i < works.size(); i++)
    {
        answer += works[i] * works[i];
    }

    return answer;
}

🧐 분석

1. priority queue를 사용하는 것이 아니라, 벡터 내장 함수인 max_element를 사용하고 있다.
2. 따로 피로도가 0아래로 내려가지 못하게 하는 로직은 처리하지 않고 있다.
   아마 문제가 개편되기 전엔 처리하지 않아도 됐던것 같다.

Programmers 카테고리 내 다른 글 보러가기