귤 고르기

문제

문제 풀이

1. 귤을 상자에 문제에서 제시한 수(k)만큼 담았을 때, 크기의 종류가 최소한이 되는 경우(Answer)를 반환하는 문제.

2. 전달받은 귤 크기대로 숫자를 세기 위해서 map<int, int>에 크기별 개수를 기록한다.

3. 크기별 개수를 정렬을 위해서 vector에 넣는다. 상자에 넣을 때, 종류의 값이 중요하지 않기 때문에 개수만 vector에 기록하는 것이다.

4. 많은 개수부터 상자에 넣기 위해서 내림차순 정렬 수행

5. 정렬된 vector의 원소별로 순회하며 귤 수를 담아준다. 반복의 시작에서 현재 박스에 들어가 있는 귤 수가 k보다 크면 반복을 멈추게 하고, 아니라면 Answer를 1개 증가(종류를 1개 증가)시키고 현재 Box에 해당 종류의 귤을 담았다 가정하여 해당 크기의 갯수만큼(해당 Index의 귤 수) 더해준다. 

 

코드

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

using namespace std;

int solution(int k, vector<int> tangerine) 
{
    // 귤을 크기별로 분류하여 개수를 센다
    map<int, int> MapTangerine;
    for(int& Tan : tangerine)
    {
        ++MapTangerine[Tan];
    }
    
    // 상자에 개수가 많은 종류부터 담으면 
    // 상자에 담긴 종류가 최소화 되므로
    // 종류별 개수를 배열에 담아 내림차순으로 정렬해준다.
    vector<int> BigToSmallArray;
    for(auto Pair : MapTangerine)
    {
        BigToSmallArray.push_back(Pair.second);
    }
    
    sort(BigToSmallArray.begin(), BigToSmallArray.end(), greater<int>());
    
    int CountInBox = 0, Answer = 0;
    for(int IDX = 0; IDX < BigToSmallArray.size(); ++IDX)
    {
        // 상자에 담긴 귤 수가 k개 이상이면 꽉찼으니 정지
        if(CountInBox >= k)
        {
            break;
        }
        
        // 종류 수 더해주고
        // 현재 상자에 담긴 귤 수를 갱신한다.
        ++Answer;
        CountInBox += BigToSmallArray[IDX];
    }
    
    return Answer;
}