Level 1. 과일 장수

Level 1. 과일 장수

 

 

사과를 점수의 역순으로 정렬한 후 앞에서부터 m개 중 가장 마지막(최저 점수) 사과를 기준으로 가격을 계산하고 해당 m개를 삭제한다.

 

하지만, 이 방법은 시간 초과가 발생했다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int k, int m, vector<int> score)
{
    int answer = 0;

    sort(score.rbegin(), score.rend());

    while (m <= score.size())
    {
        answer += score[m - 1] * m;

        score.erase(score.begin(), score.begin() + m);
    }

    return answer;
}

 

아마도 vector.erase()에서 앞 부분의 원소를 삭제하면서 계속 뒷 부분을 당겨오게 되어 시간 초과가 발생한 것 같다.

• 한 번 당겨올 때 O(n) 시간이 소요된다.

 

정순으로 정렬하고 마지막 부분을 삭제하는 방식을 사용하면 될 것 같다.

 

굳이 가격을 계산한 사과를 삭제하지 않고 인덱스를 이용해 건너 뛰면서 계산하여 시간 초과를 해결하였다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int k, int m, vector<int> score)
{
    int answer = 0;
    size_t size = score.size();

    sort(score.rbegin(), score.rend());

    for (int i = m - 1; i < size; i += m)
        answer += score[i] * m;

    return answer;
}

 

마지막은 우선순위 큐를 이용하여 해결했다.

 

가장 높은 점수의 사과를 꺼내는 것에서 아이디어를 얻었다.

 

최고점 사과부터 차례대로 꺼내어 계산한다.

 

m개를 꺼낸 후 마지막 사과의 점수를 기준으로 가격을 계산하면 된다.

 

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

using namespace std;

int solution(int k, int m, vector<int> score)
{
    int answer = 0;
    priority_queue<int> prque(score.begin(), score.end());

    while (m <= prque.size())
    {
        int min_score = 0;

        for (int i = 0; i < m; ++i)
        {
            min_score = prque.top();
            prque.pop();
        }

        answer += min_score * m;
    }

    return answer;
}