[Programmers] 귤 고르기(Lv.2)

풀이 소요시간 : 20분

확실히 BOJ 와 프로그래머스는 다른거같다. 이 문제는 언뜻 보기에 백트래킹 으로 접근해야하나 생각이 들었지만, 훨씬 간단하게 Map 으로 풀이할 수 있을거같아 그렇게 했다. 단번에 통과되었고, 풀이를 참고한 결과 정석적으로 잘 풀어낸 것 같다.

전체 코드

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

map<int, int> Map;

bool Cmp(pair<int, int> A, pair<int, int> B) {
    //first = 귤의 크기, second = 귤의 갯수
    //갯수가 많은 귤 순으로 정렬
    return A.second > B.second; 
}

int solution(int k, vector<int> tangerine) {
    
    int N = tangerine.size();
    
    for(int i = 0; i < N; i++) {
        Map[tangerine[i]]++;
    }//Map에 각 크기별 귤의 갯수 저장
    
    vector<pair<int, int>> Vector(Map.begin(), Map.end());
    sort(Vector.begin(), Vector.end(), Cmp);
    //정렬
    
    int i = 0;
    for(; i < N; i++) {
        if(k >= Vector[i].second) {
            k -= Vector[i].second;
            if(k == 0) break;
        }
        else {
            break;
        }
    }
    //종류 카운트
    
    return i + 1;
    
}