귤 고르기

문제를 해매는 가장 큰 이유 : 매번 비슷한데 갯수를 따로 한 번 더 저장을 하면 되는데 이 방식을 기억을 못함.,..

그리고 100000 연산이라고 할 때 이 연산을 2번 3번 해도 O(N) 인건데 이걸 계속 까먹으니 sort 를 쓰기 무서워함...

 

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

using namespace std;

bool Compare(int a, int b)
{
    return a > b;
}

int solution(int k, vector<int> tangerine) {
    int answer = 0;
    vector<int> food;
    
    map<int, int> food1;
    for(int i = 0; i<tangerine.size(); ++i)
    {
        food1[tangerine[i]]++;
    }
    
    for(pair<int,int> a : food1)
    {
        food.push_back(a.second);
    }
    
    sort(food.begin(), food.end(), Compare);
    
    for(int i = 0; i<food.size(); ++i)
    {
        k -= food[i];
        answer++;
        if(k <=0)
        {
            break;
        }
    }
   
    
    return answer;
}