[C++/알고리즘] 프로그래머스 (야근지수)

programmers.co.kr/learn/courses/30/lessons/12927

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

 

 

 

처음에는 이렇게 풀어서 정확성은 다 맞는데 효율성에서 시간이 초과 돼 실패했다.

그래서 뭐가 문제인지 찾아보니 이 문제는 우선순위큐를 이용해서 풀면 된다고 했다.

생각해보니 그랬다. 이전에 푼 방식같은 경우에는 제일 큰 값들을 하나씩 빼주려고 sort를 매번 루프때마다 했는데

그게 큰 요인이지 않았을까.

우선순위 큐를 하면 숫자가 제일 큰 게 제일 위로 오니까 매번 정렬을 할 필요가 없었다.

 

long long solution(int n, vector<int> works) {
    long long answer = 0;
    int works_size = works.size();
   int idx = 0;
    while( idx < n)
    {
        sort(works.begin(), works.end(), greater<int>());
        if(works[0]>0){
        works[0] -=1;
        }
        idx += 1;
    }
    
    for(int i=0;i<works_size;++i)
    {
        answer += works[i]*works[i];
    }
    return answer;
}

 

 

아래는 우선순위 큐를 이용해 수정한 방식이다.

 

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]);
    }
    
    int idx = 0;
    while(n > idx)
    {
        int temp = pq.top();
        pq.pop();
        
        if(temp > 0)
        {
            temp -=1;
        }
        
        pq.push(temp);
        
        idx+=1;
    }

    for(int i=0;i<works.size();++i)
    {
        int temp = pq.top();
        answer += temp*temp;
        pq.pop();
    }
    return answer;
}