프로그래머스 귤 고르기 [Lv. 2] (C++)

프로그래머스

상자에 담으려는 귤의 개수 K와 귤의 각 크기를 담은 배열을 입력 받을 때,  경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 구해주세요.

 

 

풀이 방법

귤의 종류의 개수를 기준으로 내림차순 정렬 후, 순서대로 개수를 더하여 K개를 넘는 위치가 어디있지 찾으면 됩니다.

 

1. map을 이용하여 귤 종류별 개수를 찾아줍니다.

map<int, int> t;
for (int n : tangerine)
    t[n]++;

 

2. map에 있는 데이터를 vector로 옮긴 후 개수를 기준으로 내림차순 정렬을 합니다.

vector<pair<int, int>> v;
for (auto p : t)
    v.push_back(p);

sort(v.begin(), v.end(), 
     [](pair<int, int> a, pair<int, int> b){return a.second > b.second;});

 

 

3. K개의 개수를 채우기위한 귤의 종류가 몇개인지 찾아줍니다.

int answer = 0;
int total = 0;
for (auto p : v)
{
    total += p.second;
    answer++;
    if (total >= k)
        break;
}

return answer;

 

 

전체 코드

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

using namespace std;

int solution(int k, vector<int> tangerine)
{
    map<int, int> t;
    for (int n : tangerine)
        t[n]++;
    
    vector<pair<int, int>> v;
    for (auto p : t)
        v.push_back(p);
    
    sort(v.begin(), v.end(), 
         [](pair<int, int> a, pair<int, int> b){return a.second > b.second;});
    
    int answer = 0;
    int total = 0;
    for (auto p : v)
    {
        total += p.second;
        answer++;
        if (total >= k)
            break;
    }
    
    return answer;
}