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

---

🔗 문제 링크

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

프로그래머스

---

728x90

👩‍💻 코드

#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

int solution(int k, vector<int> tangerine){
    int answer = 0;
    int sum = 0;
    unordered_map<int, int> categorized_tangerine;
    vector<int> counts;

    for(int t : tangerine){
        categorized_tangerine[t]++;
    }
    
    for (const auto& pair : categorized_tangerine) {
        counts.push_back(pair.second);
    }
    
    sort(counts.rbegin(), counts.rend());
    
    for(int i=0; i<counts.size(); i++){
        if(sum >= k){
            return answer;
        }
        
        sum += counts[i];
        answer++;
    }
    
    return answer;
}

---

📝 풀이

tangerine에서 무게 별로 개수를 분류하여 categorized_tangerine에 저장한다.

귤의 무게	개수
1	1
3	2
2	2
5	2
4	1

 

서로 다른 종류의 최소값을 구해야하기 때문에 귤의 개수만 필요하다.

개수만 counts에 저장하고 가장 많은 개수의 귤을 사용하기 위해 내림차순으로 정렬한다.

다른 종류의 귤을 추가할 때마다 전체 개수를 추가해주고 목표 개수를 충족하면 answer을 return한다.