Programers 귤 고르기 / C++

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

프로그래머스

 

아이디어

고른 귤의 종류가 최소가 되는 방법은 가장 개수가 많은 귤에서부터 고르는 기회를 소진시키면 됩니다.

귤과 고르는 기회를 곱하여 0이 될때 한 종류의 과일을 다고르거나 더이상 귤고르는 기회가 없을때 2가지 조건을 모두 충족시키는 조건문이 되는데, 해당 조건을 코드로 풀어낸게 문제의 히트요소입니다. 

 

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

int solution(int k, vector<int> tangerine) {
	int answer = 0;
	int sum = 0;
	unordered_map<int, int> m;
	vector<pair<int, int>> v;
	unordered_map<int, int>::iterator iter;
	for (auto iter : tangerine) m[iter]++;
	for (iter = m.begin(); iter != m.end(); iter++) v.push_back({ iter->first, iter->second });
	
	sort(v.begin(), v.end(), 
         [](pair<int, int> a, pair<int, int> b)->bool {
				return a.second > b.second; });	
    
	for (auto iter : v) {
		if (k < 1) break;
		answer++;
        //귤과 k를 곱해서 0이 될때는 한 종류의 과일을 다 고르거나 더 이상 고를 수 없을때
		while (iter.second*k) {
			k--;
			iter.second--;
		}
	}
	return answer;
}