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

https://school.programmers.co.kr/learn/courses/30/lessons/138476

프로그래머스

 

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

int solution(int k, vector<int> tangerine) {
    int answer = 1;
    unordered_map<int,int> um;
    for(int it : tangerine)
        um[it]++;
    
    vector<pair<int,int>> v;
    for(auto& it : um)
        v.push_back(it);
    
    sort(v.begin(),v.end(),[](auto& a,auto& b){return a.second>b.second;});
    
    int sum=v[0].second;
    if(sum>=k)
        return 1;
    for(int i=1;i<v.size();i++)
    {
        if(k>sum+v[i].second)
        {
            sum+=v[i].second;
            answer++;
        }
        else
        {
            answer++;
            break;
        }
    }
    return answer;
}

k개의 귤을 골라서 같은 크기대로 상자에 담았을 때, 귤의 종류가 가장 적은 경우일 때, 몇가지의 종류인지를 리턴하는 문제이다. 

따라서 같은 크기가 많은 귤부터 상자에 담는다고 하면 자연스레 귤의 종류가 최소인 경우가 된다. 

 

먼저 unordered_map 에 각 귤의 크기와 개수를 저장한다. 

이를 벡터에 옮겨서 큰 순서대로 정렬한다. 

그리고 for문을 돌며 k개가 넘을 때까지 담으면 된다. 

 

unordered_map<int,int> um;
    for(int it : tangerine)
        um[it]++;
    
    vector<pair<int,int>> v;
    for(auto& it : um)
        v.push_back(it);

맵에 값을 저장하고 각 pair를 벡터에 옮긴다. 

 

sort(v.begin(),v.end(),[](auto& a,auto& b){return a.second>b.second;});

개수를 내림차순으로 정렬한다. 

 

int sum=v[0].second;
    if(sum>=k)
        return 1;
    for(int i=1;i<v.size();i++)
    {
        if(k>sum+v[i].second)
        {
            sum+=v[i].second;
            answer++;
        }
        else
        {
            answer++;
            break;
        }
    }

먼저 한종류만 담기는 경우를 예외처리한다. 

그리고 answer를 1부터 시작하여 for문을 돈다. 

현재 i의 귤을 담았을 때 k가 안넘으면 answer를 증가시키고 sum에 더한다.

 

만약 담았을 때 k와 같거나 넘으면 그게 마지막 귤의 종류가 된다. 따라서 +1 하고 종료한다.