[ 프로그래머스 ] 귤 고르기

문제

---

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

풀이

---

서로 다른 크기의 귤을 최소 가짓수로 도출하는 문제로, 가장 적은 개수를 가진 크기부터 순서대로 더하면 되는 문제이다. map을 사용하여 같은 크기의 귤의 개수를 구하고 이를 오름차순으로 정렬한다. 각 크기 별 개수를 순서대로 더하고, 충족 시의 index를 return한다.

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

using namespace std;

int solution(int k, vector<int> tangerine) 
{
    int answer = 0;

    map<int, int> m;

    for (int i = 0; i < tangerine.size(); i++)
    {
        if (m.find(tangerine[i]) != m.end())
        {
            m[tangerine[i]]++;
        }

        else
        {
            m.insert({ tangerine[i], 1 });
        }
    }

    vector<int> arr;

    for (auto it = m.begin(); it != m.end(); it++)
    {
        arr.push_back(it->second);
    }

    sort(arr.begin(), arr.end());
    reverse(arr.begin(), arr.end());

    int res = 0;
    int cnt = 0;

    while (res < k)
    {
        res += arr[cnt];
        cnt++;

    }

    answer = cnt;

    return answer;
}