[코딩테스트 C++] 야근 지수

오늘의 문제

https://programmers.co.kr/learn/courses/30/lessons/12927#

야근 지수

나의 풀이

#include <string>
#include <vector>
#include <queue>
#include <math.h>

using namespace std;
bool cmp(int a, int b){
    return a > b;
}
long long solution(int n, vector<int> works) {
    long long answer = 0;
    
    priority_queue<int, vector<int>, less<int>> q;
    for(int i=0;i<works.size();i++)
        q.push(works[i]);
    for(int i=0;i<n;i++){
        int in = q.top();
        q.pop();
        if(in == 0)
            return 0;
        q.push(in-1);
    }

    while(q.size() != 0){
        answer += pow(q.top(), 2);
        q.pop();
    }
    return answer;
}

모범 답안

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

using namespace std;

long long solution(int n, vector<int> works) {
    long long answer = 0;
    priority_queue<int>list(works.begin(), works.end());
    int tmp;
    while (n--)
    {
        tmp = list.top();
        if (tmp > 0)
            tmp--;
        list.pop();
        list.push(tmp);
    }
    while (!list.empty())
    {
        answer += (long long)list.top() * (long long)list.top();
        list.pop();
    }
    return answer;
}

배울 점

• 로직은 정말 간단하게 제일 큰것만 빼면 된다. 이것에 대한 정확성은 증명으로 확인한 후 코드를 작성했다.
• 처음에 저번에 배웠던 multiset을 활용해서 풀었는데 효율성에서 실패를 당했다.
• 우선순위큐로하니까 성공했다. 우선순위큐는 정말 빠르다.

• queue를 초기화 하는 방법을 배웠다 begin, end를 쓰면 되는구나..