본문 바로가기

알고리즘/알고리즘 문제 풀이

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

반응형

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

문제링크 : 프로그래머스 야근 지수

 

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

회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도

programmers.co.kr

 

문제 설명

회사원 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]입니다. 이 때 야근 지수는 2^2 + 2^2 + 2^2 = 12 입니다.

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

 


풀이 과정

  1. 처음에 노트에 적어가면서 여러가지 경우의 수를 계산해보니 최대한 같은 수가 나오는게 가장 줄이는 방법인줄 알았다.
  2. 따라서 works 에 있는 모든 수들의 밸런스를 맞추려고 했으나 쉽지 않아서 다시 생각해보았다.
  3. works 내에 있는 수 중에서 가장 큰 수를 계속해서 줄여나가는 것이 피로도를 최대로 줄일 수 있는 방법임을 알았다.
  4. 따라서 우선순위 큐를 사용해서 최대값을 계속 줄여나가는 방법으로 진행을 했다.
  5. 자세한건 아래 코드에서 주석을 참고

 

코드

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

using namespace std;

// 야근 피로도 += 남은 일의 작업량^2
// n = 퇴근까지 남은 시간
// works = 각 일에 대한 작업량
// 최대값을 줄이는 것이 목표
long long solution(int n, vector<int> works) {
    long long answer = 0;

    priority_queue<int> pq;
    // 작업량을 모두 우선순위 큐에 넣으면 내부적으로 알아서 최대값이 제일 top에 위치하게 된다.
   for(auto w : works)
       pq.push(w);
    // n을 줄여나가면서 로직을 처리한다.
    while(n > 0) {
          // 이거 처리 안했다가 테스트 13 정확성 통과가 안됨
        if(pq.empty())
            break;
        // 최대값을 뽑는다.
        int front = pq.top();
        pq.pop();
        // 최대값을 하나 줄여준다.
        front--;
          // 작업량이 음수가 되는것은 말이 안된다.
        if(front < 0) {
            n--;
            continue;
        }
        // 이전에 최대값을 하나 줄여서 다시 우선순위 큐에 넣어주고 작업시간인 n을 1빼준다.
        pq.push(front);
        n--;
    }

      // 남은 작업량 처리
    while(!pq.empty()) {
        answer += (long long)pq.top() * (long long)pq.top();
        pq.pop();
    }

    return answer;
}

 

결과

반응형