C++:: 프로그래머스 < 귤 고르기 >

귤의 크기에 관계없이 원하는 개수만큼 최대한 적은 종류를 선택하면 되는 문제이다. 무게당 몇개인지를 체크하고 개수가 많은 순으로 정렬하여 원하는 개수를 채워주면 가장 최소 종류를 알 수 있는 문제이다.

#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

bool compare(pair<int, int>a, pair<int, int>b)
{
    return a.second > b.second;//무게별 개수 내림차순정렬
}

int solution(int k, vector<int> tangerine)
{
    int answer = 0, cnt=0;
    map<int,int> m;
    vector<pair<int, int>> v;
    for(auto c : tangerine) m[c]++;
    for(auto c : m) v.push_back({c.first, c.second});//무게, 개수
    sort(v.begin(), v.end(), compare);
    for(int i=0;i<v.size();i++)
    {
        cnt += v[i].second;
        if (cnt >= k) return (i+1);// 목표 개수를 넘기거나 같다면
    }
    return -1;
}