과일 장수

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

프로그래머스

 

 

#include <string>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

// k : 최고 점수
// m : 포장할 수 있는 사과 갯수
// score : 사과의 점수
// 사과의 최종 점수는 사과의 가장 낮은 점수 기준으로 환산

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

    if(score.size() < m) {
        return 0;
    }
    
    // SORT
    sort(score.begin(), score.end());
    
    // 큰 점수들 먼저 묶기
    while(score.size() >= m){

        // Find the min score
        int p = k;
        
        int cnt = 0;
        while(cnt < m){
            cnt++;
            
            if(p > score.back())
                p = score.back();
            score.pop_back();
        }

        // Sum the score with min value
        int total_min_score = 0;
        total_min_score = p * m;
        
        total_score += total_min_score;
    }
    
    cout << "total_score = " << total_score << endl;
        
    return total_score;
}

 

<풀이>

0. 만약 score 벡터의 크기가 포장할 수 있는 사과 갯수 m보다 작다면 0을 반환합니다.

1. sort() 함수를 이용해서 오름차순으로 정렬 했습니다.

2. score 벡터의 크기가 포장할 수 있는 사과 갯수 m보다 작을 때만 반복합니다.

3. 포장 박스 안에 담긴 m개의 사과 중에서 최소 점수를 찾습니다. (=p)

   3-1. back() 함수를 이용하여 벡터의 마지막 값을 확인

   3-2. pop_back() 함수를 이용하여 벡터의 마지막 값을 pop

4. 사과를 포장할 때마다 벡터의 마지막 데이터를 pop 해줍니다.

5. 최소 점수를 이용하여 포장 박스의 점수를 구합니다.

6. 모든 포장 박스의 점수를 합산합니다.

 

 

다른 사람들이 풀어본 풀이를 보면..

@binaryrain97 님의 풀이입니다.

#include <vector>
#include <queue>

using namespace std;

priority_queue<int> pq;

int solution(int k, int m, vector<int> score) {
    int answer = 0;
    for(int i=0; i<score.size(); i++)
        pq.push(score[i]);
    while(pq.size() >= m) {
        for(int i=0; i<m-1; i++) pq.pop();
        answer += pq.top() * m;
        pq.pop();
    }
    return answer;
}

 

priority_queue를 사용하여 구현을 했습니다.

 

<풀이>

1. 우선순위 큐에 score 데이터를 다 집어 넣습니다. (=이 때, 이미 정렬이 됩니다.)

2. 우선순위 큐의 전체 크기가 m보다 크거나 같을 때만 반복합니다.

3. 총 m-1개 만큼 pop() 시킵니다. (어짜피 pop() 함수를 다 실행시키고 나서 마지막에 남은 데이터가 min 값이기 떄문에 굳이 min 값을 찾을 필요 없었네요)

4. 최소 값을 찾기 위해 우선 순위 큐에서 top() 함수를 이용하여 찾고, m개만큼 곱해줍니다.

5. 마지막 사과를 pop() 해줍니다.