귤 고르기/C++

프로그래머스

박스에 담아 판매할 때 귤의 크기의 종류가 최소가 되어야 하므로 개수가 많은 크기의 귤을 차례대로 담아주면 된다.

이를 위해 map을 사용해 귤의 크기를 key값 개수를 value로 하여 저장하고 이를 value 값에 따라 오름차순으로 정렬한 다음 크기가 많은 순서대로 담아 합이 k이상이 됐을 때의 종류의 수를 리턴하였다.

 

풀이 방법

1. int형을 각각 key,value로 가지는 m을 선언한다.

2. tangerine을 m에 담는다.

3. 벡터에 담고 value 값에 따라 오른차순으로 정렬한다.

4. value값을 더하며 합이 k이상이 되면 더한 횟수 count를 리턴한다.

 

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

using namespace std;

bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
    if(a.second == b.second) return a.first > b.first;
    else return a.second > b.second;
}

int solution(int k, vector<int> tangerine) {
    int count = 0;
    int tmp = 0;
    
    map<int, int> m;
    
    for(int i = 0; i < tangerine.size(); i++)
            m[tangerine[i]]++;
    
    vector<pair<int, int>> v(m.begin(), m.end());
    
    sort(v.begin(), v.end(), cmp);
    
    for(int i = 0; i < v.size(); i++) {
        tmp += v[i].second;
        count++;
        
        if (tmp >= k) return count;
    }
}