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

문제

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

프로그래머스

 

 

해시 기반으로 크기에 대한 갯수를 받음.

갯수를 기반으로 정렬하기 위해 priority_queue를 사용

-> 자동적으로 갯수가 많은 것부터 정렬됨.

#include <bits/stdc++.h>

using namespace std;
/*
k : 귤의 갯수
종류를 최소화하여 귤을 판매

1) 해시 
2) pq를 사용해 갯수가 많은 순으로 정렬
*/

int solution(int k, vector<int> tangerine) {
    int answer = 0;
    unordered_map<int,int> cnt;          // (크기 -> 개수)
    for (int x : tangerine) cnt[x]++;

    
    priority_queue<pair<int,int>> pq;     // top: count 가장 큰 것
    for (auto &p : cnt) pq.push({p.second, p.first});   // (갯수, 크기) 순으로 추가 -> 자동으로 크기가 큰 것 부터 정렬됨.

    
    while (!pq.empty()) 
    {
        // cout << pq.top().first << " " << pq.top().second << "\n";
        k-= pq.top().first;
        pq.pop();
        answer++;
        if(k<=0) 
            break;
    }
    
    
    return answer;
}