프로그래머스 [연습문제 / 과일 장수](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 과일 장수

---

문제 링크: 문제 보기

문제 설명:

과일 장수가 사과를 상자 단위로 포장하여 판매할 때, 한 상자에 m개씩 포장합니다. 이때 한 상자의 가격은 가장 낮은 사과 점수 × m이며, 사과 점수는 score 배열로 주어집니다. 상자를 최대한 많이 만들고, 총 이익을 구하는 문제입니다.

---

문제 해결 코드

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

using namespace std;

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

    // 점수를 내림차순 정렬
    sort(score.begin(), score.end(), greater<>());

    // m개씩 묶어서 최솟값 * m 만큼 수익 계산
    for (int i = 0; i + m - 1 < score.size(); i += m) {
        answer += score[i + m - 1] * m;
    }

    return answer;
}

---

코드 설명

• 핵심 알고리즘: 점수를 내림차순 정렬한 후, 높은 점수부터 묶어서 m개씩 상자를 만든다. 묶은 상자에서 가장 낮은 점수를 곱하여 상자 가격을 계산한다.
• 구현 세부사항:
• sort(score.begin(), score.end(), greater<>())를 통해 내림차순 정렬
• 각 상자는 연속된 m개로 구성되며, 마지막 점수가 최소 점수
• 상자 단위로만 계산하므로, 남는 사과는 무시함
• 시간 복잡도 분석:
• 정렬: O(n log n)
• 상자 계산: O(n)
• 총 시간 복잡도: O(n log n)

---

결과

이 코드는 사과 점수를 내림차순 정렬한 후, 높은 점수부터 상자를 만들어 가장 효율적인 방식으로 이익을 계산합니다. 남는 사과는 버려도 되므로, 상자 단위만 고려하면 됩니다.

다른 접근 방식으로는 최소 힙(min-heap)을 이용하여 최솟값을 빠르게 추출하는 방법도 있지만, 이 문제에서는 정렬 후 인덱스로 접근하는 것이 더 간단하고 효율적입니다.