과일장수

 

*초기 작성 코드

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

void check_apple(unordered_map<int, int>& List, int k, const vector<int>& score)
{
    for (int i = 1; i <= k; ++i)
    {
        int k_cnt = count(score.begin(), score.end(), i);

        List[i] = k_cnt;
    }
}

int solution(int k, int m, vector<int> score)
{
    unordered_map<int, int> apple_cnt;
    int result = 0;

    // score 점수별로 사과가 몇 개 있는지 정리
    check_apple(apple_cnt, k, score);

    // k점수부터 1점수까지 m개씩 포장해서 점수 계산
    for (int i = k; i >= 1; --i)
    {
        // 만약 개수가 m보다 작다면 밑에 점수 개수에 저장
        if (apple_cnt[i] < m)
        {
            apple_cnt[i - 1] += apple_cnt[i];
            continue;
        }

        // m으로 나눈 몫 * 점수를 result에 더해 저장
        result += (apple_cnt[i] / m) * i * m;

        // 나머지를 밑에 점수 개수에 저장
        apple_cnt[i - 1] += apple_cnt[i] % m;
    }


    return result;
}

• unordered_map을 사용해서 score의 점수 별로 사과가 몇 개 있는지 먼저 정리한 후 이 리스트를 가지고 최대 이익을 계산하는 방향으로 코드를 작성했다.
• 문제에서 score의 크기가 1,000,000까지 아주 많은 경우가 생길 수 있는데, 현재 코드에서 count함수를 사용해 score 크기 만큼 루프를 k번이나 돌아야해서 비효율적이라는 생각이 들었다.
• 루프를 최소화 하는 방향으로 다시 코드를 작성하려 고민했다.

 

*수정 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;


int solution(int k, int m, vector<int> score)
{
    int result = 0;
    // score 내림차순으로 정렬
    sort(score.begin(), score.end(), greater<>());

    // i는 m씩 증가, i + m이 score.size를 초과하기 전까지 반복
    for(int i = 0; i + m <= score.size(); i += m)
    {
        // 내림차순 정렬했기 때문에 m번째 요소가 박스에 들어갈 최소 점수
        int min_score = score[i + m - 1];

        // 최소 점수 * 개수를 저장
        result += min_score * m;
    }


    return result;
}

• 우선 score를 내림차순으로 정렬해주었다.
• 정렬이 되었기 때문에, m번째 요소가 한 박스의 최소 점수가 되고 이를 m으로 다시 곱해 그 박스의 이익을 계산하였다.
• 별도의 추가 컨테이너도 사용하지 않았고, 1개의 루프로 해결할 수 있어서 시간 또한 세이브되었다고 보여진다.

 

요즘 문제를 풀면서 더 효율적인 방법이 없을지 계속 생각하다 보니, 이것 저것 불필요한 컨테이너를 사용하게 되면서 오히려 과정이 더 많아져 코드가 복잡해지고 비효율적인 결과가 나오는 듯하다..:(