[프로그래머스] 과일 장수 in C++

(제가 생각한 솔루션이므로 최적의 솔루션이 아닐 수 있습니다..!)

 

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/135808

프로그래머스

 

1. 문제 이해

문제에서 주어지는 입력값은 총 세 개입니다.

k : 문제에서 주어지는 사과의 최댓값

m : 한 상자에 들어가는 사과의 수

score : 모든 사과들의 점수 (vector<int>)

 

위 값들이 주어졌을 때, 사과를 어떤 식으로 상자에 포장해서 그 가격의 합이 최대가 되도록 하는 것이 이 문제의 목적입니다.

 

사과 장수가 같은 개수의 사과를 각 상자에 포장해서 가격을 결정하려고 합니다.

이때 각 상자의 가격은 다음과 같이 계산됩니다.

(상자 안의 사과 중 가장 낮은 점수) * (상자 안의 사과의 개수)

 

예를 들어, 한 상자당 5개의 사과를 포장하려고 하고 다음과 같이 총 두 개의 상자로 담겨졌다고 합시다.

[3, 4, 3, 2, 2], [4, 1, 3, 3, 3]

첫 상자 안에 담긴 사과 중 가장 낮은 점수는 2 이므로 첫 상자의 가격은 2 * 5,

두번째 상자 안에 담긴 사과 중 가장 낮은 점수는 1이므로 두번째 상자의 가격은 1 * 5,

총 가격은 2 * 5 + 1 * 5 = 15 가 될 것입니다.

 

2. 풀이법 연상

모든 사과의 개수와 각 상자 내 담길 사과의 갯수는 이미 정해져 있습니다.

따라서 각 상자에 담길 사과들 중 가장 낮은 점수의 사과만 점수가 최대가 될 수 있도록 하면 되겠다고 생각했습니다.

그러기 위해서는 낮은 점수대의 사과와 높은 점수대의 사과가 섞이면 안되겠다고 생각했습니다.

 

예를 들어 1, 2, ..., 10 까지의 사과를 5개씩 포장한다고 할때,

1) [10, 9, 8, 7, 6], [5, 4, 3, 2, 1]

위와 같이 높은 점수와 낮은 점수의 사과를 구분짓는 방법과

2) [10, 1, 9, 8, 7], [6, 5, 4, 3, 2]

방법을 비교해보면,

자연스럽게 1) 방법이 더 점수가 높을 것임을 알 수 있습니다.

 

그래서 가장 처음 생각난 풀이법은 정렬이었습니다.

 

모든 사과를 점수에 대해서 내림차순으로 정렬시키고, 각 상자 내 사과의 갯수만큼 나누어 포장하면 높은 점수대의 사과와 낮은 점수대의 사과를 나누어 포장할 수 있을거라고 생각했습니다.

추가로 각 상자 내에 담길 사과들 중 가장 낮은 점수만 구하면 되므로 정렬을 통해 그 값을 쉽게 구할 수 있을 거라 예상했습니다.

 

 

3.  풀이에 필요한 지식

C++의 STL 중 algorithm 라이브러리의 sort 함수를 사용하기로 했습니다.

 

sort(vector.begin(), vector.end(), eval_function)

 

sort 함수의 첫번째 인자에는 배열의 시작 포인터, 두번째 인자에는 배열의 마지막 포인터, 세번째 인자에는 사용자가 직접 정의해서 어떤 특수한 규칙을 따르는 정렬을 하도록 합니다. 아무 함수도 받지 않는 경우 오름차순을 기본적으로 하게 됩니다.

 

4. 코딩

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

using namespace std;

// sort의 내림차순 위한 함수 정의
bool cmp(int x, int y){
    return x > y;
}

int solution(int k, int m, vector<int> score) {
    int answer = 0;
    
    // 사과의 총 개수
    int score_size = score.size();
    
    // 내림차순 정렬
    sort(score.begin(), score.end(), cmp);
    
    for(int i=0;i < score_size / m;i++){
    	// 각 상자 중 가장 낮은 사과의 점수 * 각 상자의 사과 개수
        answer += score[(i + 1) * m - 1] * m;
    }
    return answer;
}