선밥의 공부하는 블로그

과일 장수

문제 링크

과일 장수

분석

상자를 최대한 많이, 높은 점수의 사과들로 판매하는 것이 최대 이익을 낼 수 있습니다.

score를 내림차순으로 정렬한 후 배열의 값을 확인합니다.
상자의 가장 낮은 값으로 m개씩 판매한 값을 반환값에 저장한 후 반환합니다.

풀이

#include <vector>
#include <algorithm>

using namespace std;

int solution(int k, int m, vector<int> score) {
    int answer = 0;
    std::vector<int> box;
    int minScore = 0;
    
    sort(score.rbegin(), score.rend());
    
    for (int i = 0; i < score.size(); ++i)
    {
        box.push_back(score[i]);
        
        if (minScore < score[i])
        {
            minScore = score[i];
        }
        
        if (box.size() == m)
        {
            answer += minScore * m;
            box.clear();
        }
        
        minScore = 0;
    }
    
    return answer;
}

정렬된 score배열을 순회하며, 사과 상자의 가장 작은 값과 상자에 사과 1개를 저장합니다.

상자의 개수를 다 채웠을 때 판매 가격을 저장합니다.

위의 알고리즘을 리팩토링 해보았습니다.

#include <vector>
#include <algorithm>

using namespace std;

int solution(int k, int m, vector<int> score) {
    int answer = 0;
    
    sort(score.rbegin(), score.rend());
    
    for (int i = 0; i + m <= score.size(); i += m)
    {
        answer += score[i + m - 1] * m;
    }
    
    return answer;
}

반복문은 묶음 단위인 m의 크기로 만들 수 있은 상자의 개수만큼 반복합니다.

정렬한 배열이므로 m - 1번째에 해당 묶음의 가장 작은 값이 들어있습니다.
이 가장 작은 값으로 최종 판매 가격을 구합니다.

성능 요약

시간 복잡도는 내림차순 정렬($O(n \, log \, n)$)과 score를 순회하는 반복문($O(n)$)이 있기 때문에 $O(n \, log \, n)$입니다.
공간 복잡도는 $O(n)$입니다.

테스트 1 〉 통과 (0.01ms, 4.21MB)
테스트 2 〉 통과 (0.01ms, 3.68MB)
테스트 3 〉 통과 (0.01ms, 4.22MB)
테스트 4 〉 통과 (0.01ms, 4.06MB)
테스트 5 〉 통과 (0.01ms, 4.15MB)
테스트 6 〉 통과 (1.45ms, 5.28MB)
테스트 7 〉 통과 (1.82ms, 5.78MB)
테스트 8 〉 통과 (0.25ms, 4.21MB)
테스트 9 〉 통과 (1.76ms, 5.66MB)
테스트 10 〉 통과 (1.25ms, 5.04MB)
테스트 11 〉 통과 (23.85ms, 34.6MB)
테스트 12 〉 통과 (24.19ms, 34.6MB)
테스트 13 〉 통과 (23.44ms, 34.7MB)
테스트 14 〉 통과 (24.91ms, 34.7MB)
테스트 15 〉 통과 (24.21ms, 34.7MB)
테스트 16 〉 통과 (0.01ms, 4.21MB)
테스트 17 〉 통과 (0.01ms, 4.22MB)
테스트 18 〉 통과 (0.01ms, 4.21MB)
테스트 19 〉 통과 (0.01ms, 4.21MB)
테스트 20 〉 통과 (0.01ms, 4.22MB)
테스트 21 〉 통과 (0.01ms, 4.16MB)
테스트 22 〉 통과 (0.01ms, 3.68MB)
테스트 23 〉 통과 (0.01ms, 4.13MB)
테스트 24 〉 통과 (0.01ms, 4.18MB)

리팩토링한 코드의 시간복잡도와 공간복잡도는 같습니다.

테스트 1 〉 통과 (0.01ms, 4.2MB)
테스트 2 〉 통과 (0.01ms, 4.14MB)
테스트 3 〉 통과 (0.01ms, 4.2MB)
테스트 4 〉 통과 (0.01ms, 4.21MB)
테스트 5 〉 통과 (0.01ms, 3.68MB)
테스트 6 〉 통과 (1.35ms, 5.25MB)
테스트 7 〉 통과 (1.66ms, 5.66MB)
테스트 8 〉 통과 (0.23ms, 4.2MB)
테스트 9 〉 통과 (1.59ms, 5.76MB)
테스트 10 〉 통과 (1.17ms, 5.06MB)
테스트 11 〉 통과 (23.62ms, 34.6MB)
테스트 12 〉 통과 (22.70ms, 34.5MB)
테스트 13 〉 통과 (21.51ms, 34.6MB)
테스트 14 〉 통과 (23.02ms, 34.7MB)
테스트 15 〉 통과 (22.96ms, 34.5MB)
테스트 16 〉 통과 (0.01ms, 4.21MB)
테스트 17 〉 통과 (0.01ms, 4.29MB)
테스트 18 〉 통과 (0.01ms, 4.02MB)
테스트 19 〉 통과 (0.01ms, 4.2MB)
테스트 20 〉 통과 (0.01ms, 4.16MB)
테스트 21 〉 통과 (0.01ms, 3.59MB)
테스트 22 〉 통과 (0.01ms, 4.2MB)
테스트 23 〉 통과 (0.01ms, 4.14MB)
테스트 24 〉 통과 (0.01ms, 4.25MB)

Programmers 카테고리 내 다른 글 보러가기

댓글남기기

최근 글