KiTFOx's Notepad 📝

1. 문제 요약

k 개를 골라 상자 하나에 담아 판매
귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶음

처음에는 문제가 헷갈렸는데 결국 같은 크기의 귤을 모아서 최대한 판매하려고 하는 문제이다

2. 코드

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

using namespace std;


bool cmp(const pair<int,int>& lValue,const pair<int,int>& rValue){
    return lValue.second>rValue.second;
}

int solution(int k, vector<int> tangerine) {
    int answer = 0;
    
    vector<pair<int,int>> tangerinePair;
    
    sort(tangerine.begin(),tangerine.end());
    
    /*for(int i=0;i<tangerine.size();i++){
        printf("%d ",tangerine[i]);
    }
    printf("\n");*/
    
    int prev = tangerine[0];
    tangerinePair.push_back(make_pair(tangerine[0],0));
    for(int i=0;i<tangerine.size();i++){
        //printf("%d ",tangerine[i]);
        if(prev==tangerine[i]){
            tangerinePair[tangerinePair.size()-1].second++;
        }
        else{
            tangerinePair.push_back(make_pair(tangerine[i],1));
            prev=tangerine[i];
        }
    }
    //printf("\n");
    
    sort(tangerinePair.begin(),tangerinePair.end(),cmp);
    
    int count=0;
    for(int i=0;i<tangerinePair.size();i++){
        //printf("%d %d\n",tangerinePair[i].first,tangerinePair[i].second);
        if(count>=k) break;
        count+=tangerinePair[i].second;
        answer++;
    }
    
    
    return answer;
}

3. 해설

먼저 vector<int> tangerine 벡터를 오름차순으로 정렬합니다

정렬한 다음  vector<pair<int,int>> tangerinePair에 <귤의크기,갯수>를 담았다

int prev = tangerine[0];
tangerinePair.push_back(make_pair(tangerine[0],0));

for(int i=0;i<tangerine.size();i++){
    if(prev==tangerine[i]){
        tangerinePair[tangerinePair.size()-1].second++;
    }
    else{
        tangerinePair.push_back(make_pair(tangerine[i],1));
        prev=tangerine[i];
    }
}

그 후, 귤의 갯수에 따라 vector<pair<int,int> tangerinePiar를 정렬해주었다

sort(tangerinePair.begin(),tangerinePair.end(),cmp);

bool cmp(const pair<int,int>& lValue,const pair<int,int>& rValue){
    return lValue.second>rValue.second;
}

그리고 for문을 이용하여 중복되는 갯수들을 k와 비교하여 더해줘서 수를 넘어가면 break하도록 제작하여주었다

int count=0;
for(int i=0;i<tangerinePair.size();i++){
    if(count>=k) break;
    count+=tangerinePair[i].second;
    answer++;
}