프로그래머스 귤 고르기 c++

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

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> tangerineSize;
    
    for(int i=0; i<tangerine.size(); i++) {
        tangerineSize[tangerine[i]]++;
    }
    vector<pair<int,int>> vec(tangerineSize.begin(),tangerineSize.end());
    sort(vec.begin(),vec.end(),cmp);
    
    int presentSize = 0;
    
    for(int i=0; i<vec.size(); i++) {
        presentSize = presentSize + vec[i].second;
        answer++;
        if(presentSize >= k) break;
    }
    
    return answer;
}

프로그램 흐름

1. 귤의 크기별 개수 저장 ( map 컨테이너 사용 )

2. 정렬을 위해 map 컨테이너의 원소들을 vector pair 안에 저장

3. vector 내림차순 정렬

4. 귤의 개수가 k 이상이 될때까지 크기순으로 내려가며 더해줌

 

**

귤의 개수가 최대 100,000 개 이므로 2중 for 문을 사용할시 시간이 10초를 넘김.

2중 for 문을 사용하지 않으면서 시간복잡도를 최소화 하기위해 map 컨테이너 사용