프로그래머스 LV.3 야근 지수

 
 
 
 
야근 지수는 무작정 큰 수 하나만 남은 시간을 전부 할애하여
차감한다고 답이 나오는 것이 아니다.
즉 차감의 우선순위가 있기 때문에 우선순위 큐를 떠올라야 한다.
 
예를 들어 " 4, 3, 3 " 가 주어졌을 때, 4시간의 시간이 주어지면 
 
"2, 2, 2"으로 만들어야 제곱의 합이 제일 작고 "0, 3, 3"로 만들면 제곱의 합이 크다는 것을 알 수 있다.
 
그러므로, 우선순위 큐를 활용해서 존재하는 작업 중
가장 큰 값이 top인 max heap으로 구성하여
N시간 동안 top에 위치한 작업량을
잠깐 끄집어내서 한 시간씩 빼주고 다시 push 해준다. 
 
물론 vector sort로 계속 정렬할 수 있지만,
이는 vector만 사용한 코드의 시간 복잡도는 O(n*m)이므로
n번 처리하는 과정에서 매번 m개의 작업을 전부 탐색해야 한다.
비교해 보면, 우선순위 큐를 사용한 코드의 시간 복잡도가 O(nlog(m))로 더 낮다.
이는 우선순위 큐가 효율적으로 가장 큰 작업량을 찾기 때문이다.
반면에 vector만 사용한 코드는 모든 작업을 매번 탐색해야 하므로 시간 복잡도가 더 높은 O(nm)이 된다.
따라서 일반적인 경우에는 우선순위 큐를 사용한 코드가 더 효율적이다.
 
또한 works의 원소가  50000 이하인 자연수 이므로 제곱했을 때 int의 길이를 넘어설 수 있으므로
long long으로  표기하는 것이 좋다.
 
 
우선순위 큐를 사용하는 경우의 코드

long long solution(int n, vector<int> works) {
    long long answer = 0;

    priority_queue<int> q;
    for (int i = 0; i < works.size(); i++)
    {
        q.push(works[i]);
    }
    int temp;
    while (!q.empty() && n != 0)
    {
        n--;
        temp = q.top();
        q.pop();
        if (temp != 1) q.push(temp - 1);
    }
    while (!q.empty())
    {
        answer += (q.top() * q.top()); 
        q.pop();
    }


    return answer;
}

 
 
vector를 사용하는 경우의 코드

long long solution(int n, vector<int> works) {
    long long answer = 0;

    for (int i = 0; i < n; i++) {
        std::sort(works.begin(), works.end());
        std::reverse(works.begin(), works.end());
        works[0] -= 1;
    }

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

    return answer;

}

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

프로그래머스