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

문제 링크

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

내 풀이

map 을 이용하여 귤의 크기와 갯수를 구한다.
귤의 갯수만 vector에 옮겨 담은 후 내림차순으로 정렬한다.
가장 갯수가 많은 것 부터 sum에 더해나가면서 answer++을 해주고 sum이 k를 넘으면 바로 멈춘다.

내 코드

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

using namespace std;

int solution(int k, vector<int> tangerine) {
    int answer = 0;
    
    map<int,int> m;    
    for(int t : tangerine)
        m[t]++;
    
    vector<int> vec;
    
    for(auto n : m)
        vec.push_back(n.second);
    
    sort(vec.begin(), vec.end(), greater<int>());
    
    int sum = 0;
    for(int v : vec)
    {
        if(sum >= k)
            break;
        sum += v;
        answer++;
    }
    
    return answer;
}

다른 사람의 풀이

#include <bits/stdc++.h>

using namespace std;

int solution(int k, vector<int> tangerine) {
    int answer = 0;
    int m = *max_element(tangerine.begin(), tangerine.end());
    vector<int> v(m, 0);
    for(auto& t : tangerine){
        v[t - 1]++;
    }
    stable_sort(v.rbegin(), v.rend());
    for(int i = 0 ; i < v.size() ; i++){
        answer++;
        k -= v[i];
        if(k <= 0) return answer;
    }
    return answer;
}

다른 사람의 풀이 해석

tangerine 에서 가장 값이 큰 원소를 찾아서 그 원소의 개수만큼 0으로 초기화된 벡터를 만든다.
그 다음 for문으로 size에 맞는 개수를 취합한다. map으로 하는 것과 같은것 같다.
stable_sort( 값이 같은 원소가 있어도 정렬시 기존 순서를 유지해준다. )
를 이용해서 rbegin, rend로 정렬 ( 내림차순 )
그 후 첫 원소부터 answer++한 뒤 k에서 빼나가면서 k가 0 이하가 되면 answer를 리턴한다.