알고리즘(C++) / 프로그래머스 level 3 : 야근 지수

level 3 : 야근 지수

https://programmers.co.kr/learn/courses/30/lessons/12927?language=cpp 

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

 

코드

//프로그래머스 야근 지수
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

long long solution(int n, vector<int> works) {
    long long answer = 0;
    priority_queue<int> pq; //우선순위 큐
    for (int i = 0; i < works.size(); i++) {
        pq.push(works[i]);
    }

    for (int i = 0; i < n; i++) {
        if (pq.empty())
            break;
        int num = pq.top();
        pq.pop();
        //0이 아닐때 push
        if (num - 1 != 0)
            pq.push(num - 1);
    }
    
    while (!pq.empty()) {
        answer += pow(pq.top(), 2); //제곱
        pq.pop();
    }

    return answer;
}

int main() {
    int n = 4;
    vector<int> works = { 4,3,3 };
    cout << solution(n, works) << "\n";
    return 0;
}

 

설명

• 자동으로 정렬해주는 queue, priority_queue를 사용한다.
• works를 priority_queue에 push하면 내림차순으로 정렬된 것을 확인할 수 있다.
• 야근 지수를 최소화하기 위해서는 일의 작업량의 수가 작아야한다. 그러므로 가장 큰 수에서 1을 감소시켜 저장한다.
• 이때 1을 감소시킨 수가 0이라면 작업량이 없으므로 push하지 않는다.
• pow함수를 이용하여 남아있는 작업수를 모두 제곱하여 더한다. 

 

고찰

걸린 시간 : 25분

level 3치고는 쉬운 문제였다.

queue을 사용하여 문제를 풀다가 자동 정렬해주는 priority_queue 우선순위 큐가 있다는 사실을 깨닫고 쉽게 문제를 풀 수 있었다.