[프로그래머스] 귤 고르기 (C++)

문제

프로그래머스

풀이

이 문제는 1 ~ 1000000 범위의 랜덤한 크기를 가지고 있는 귤을 k개 판매할 때, 판매한 귤 크기의 최소 갯수를 반환하는 문제이다.

 

난 맵을 이용하여 각 크기별 귤의 갯수를 구하고, value 기준으로 내림차순 정렬한 뒤, 갯수가 많은 크기의 귤 먼저 귤을 판매하여 귤 크기의 최소 갯수를 구했다.

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

using namespace std;

unordered_map <int, int> boxMap;

bool cmp (pair<int,int> box01, pair<int,int> box02){
    return box01.second > box02.second;
}

int solution(int k, vector<int> tangerine) {
        
    for(int i = 0; i< tangerine.size(); i++){
        boxMap[tangerine[i]]++;
    }
    
    vector<pair<int,int>> vec (boxMap.begin(), boxMap.end());
    sort(vec.begin(), vec.end(), cmp);
    
    int idx = 0;
    for(idx =0 ; idx< vec.size(); idx++){
        k -= vec[idx].second;
        if(k <= 0)
            break;
    }
    return idx + 1;
}