프로그래머스 / 귤 고르기 / C++

C++의 컨테이너 중 하나인 map을 알면 쉽게 해결할 수 있는 문제였습니다 ! 체감상 다른 Lv2 문제들 보다는

쉬운 편이었습니다. 따로 함정이 존재하지도 않고 생각한대로 구현해서 바로 맞은 몇 안되는 문제였습니다.

 

map은 key값과 value값을 함께 가질 수 있기 때문에 크기를 key값으로 그리고 그 갯수를 value로 insert 해줍니다.

그러면 map에는 귤의 크기와 그 크기를 가진 갯수가 저장되어있고, 정렬을 위해 vector 컨테이너로 옮겨서 크기별로 내림차순으로 정렬합니다. 그러면 갯수들이 많은 귤의 크기정보순으로 정렬이 되고, 담고자 하는 k에서 맨 앞에서부터 그 크기대로 값을 빼주면서 갯수를 카운팅합니다. 그렇게 0이되거나 0보다 작을때까지 계속 빼주면 서로 다른 종류의 최솟값을 쉽게 구할 수 있습니다 !

 

 

#include <string>
#include <vector>
#include <algorithm>
#include <map>
 
using namespace std;
 
bool cmp(const pair<int,int>& a, const pair<int,int>& b)
{
    return a.second > b.second;
}
 
int solution(int k, vector<int> tangerine) {
    int answer = 0;
    map<int,int> m; //크기,갯수
    
    for (int i=0;i<tangerine.size();i++)
    {
        m[tangerine[i]]++;
    }
    
    vector<pair<int,int>> v; //(map.begin(), map.end())
    for (auto& it : m)
    {
        v.push_back({it.first,it.second});
    }
    sort(v.begin(),v.end(),cmp);
        
    int idx = 0;
    while(k>0)
    {
        k -= v[idx].second;
        idx++;
    }
    
    return idx;
}
}