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

문제설명

알고리즘

1. 귤의 크기 별 몇 개 존재하는 지 카운트 -> (key, value) 형태인 map이 가장 적절

2. MAP에 넣은 뒤, 귤의 갯수 기준으로 내림차순 정렬 

3. 벡터로 변환하여 벡터 순회하여 k 개에서 최대 귤 수 부터 k 값 감소 시키기 & 결과 값 증가

코드

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

using namespace std;
bool cmp (const pair<int,int> &a, const pair<int,int> &b){
    if(a.second == b.second)
        return a.first > b.first;
    return a.second > b.second;
}

int solution(int k, vector<int> tangerine) {
    int answer = 0;
    map<int, int> m; 
    
    for(int i: tangerine){
        if(m.find(i)!= m.end()) //키가 있는지 찾고 있으면 증가 
            m[i]+=1;
        else // 없으면 새로운 값 넣기 
            m.insert(pair<int, int>(i,1));
    }
    vector<pair<int,int>> list(m.begin(), m.end()); //벡터로 변환
    sort(list.begin(), list.end(), cmp); // value 가 되는 귤의 수를 기준으로 내림차순 정렬 수가 같은 경우 귤의 무게로 
    
    for(int i; i < list.size(); i++){ //리스트를 순회하여 귤의 가짓수 출력
        int current = list[i].second; 
        k -= current;
        if(k<=0){ // 최대 귤의 수가 귤의 갯수보다 작아질 때 종료 
            answer++;
            break;
        }
        answer++; 
    }
     
    return answer;
}

고찰