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

문제 설명

---

제한 사항 및 입출력 예제

---

개념

　주어진 배열에서 k개를 선택하는 방법 중 종류를 가장 적게 고르는 방법을 구하는 문제다. 배열을 내림차순으로 정렬하고, 가장 많은 개수를 가진 귤의 크기부터 선택하여 바구니에 담는 그리디 알고리즘을 채택하여 문제를 효율적으로 해결할 수 있다.

---

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

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

    for (const auto& val : tangerine)
        m[val]++;

　주어진 벡터에 있는 원소들의 개수를 파악하기 위해 map 자료구조를 활용하였다. 이때 맵은 귤의 크기를 키로 하고, 그 키그의 귤의 개수를 값으로 갖는다.

 

bool custom(pair<int, int>& a, pair<int, int>& b)
{
    return a.second > b.second;
}

int solution(int k, vector<int> tangerine)
{
	...
    vector<std::pair<int, int>> v(m.begin(), m.end());
    sort(v.begin(), v.end(), custom);

　그리고 벡터를 (귤의 크기, 개수)의 형태로 초기화한 후, 개수를 내림차순으로 정렬해준다.

 

    for (const auto& val : v)
    {
        if (sum >= k)
            break;

        else
        {
            sum += val.second;
            answer++;
        }
    }

    return answer;
}

　가장 많은 개수를 가진 귤의 크기부터 선택하고, 선택된 귤의 개수가 k 이상이 될 때까지 반복하면 문제를 해결할 수 있다.

 

총합본

#include <algorithm>
#include <vector>
#include <map>
using namespace std;

bool custom(pair<int, int>& a, pair<int, int>& b)
{
    return a.second > b.second;
}

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

    for (const auto& val : tangerine)
        m[val]++;

    vector<std::pair<int, int>> v(m.begin(), m.end());
    sort(v.begin(), v.end(), custom);

    for (const auto& val : v)
    {
        if (sum >= k)
            break;

        else
        {
            sum += val.second;
            answer++;
        }
    }

    return answer;
}