프로그래머스 귤 고르기

 

우선 나의 첫 풀이방식이다

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

using namespace std;

int cmp(vector<int>& a, vector<int>& b) {
    return a[0] > b[0];
}

int solution(int k, vector<int> tangerine) {
    
    vector<vector<int>> pair(10000001, vector<int>(1, 0));
    int answer = 0;

    
    for(auto x: tangerine) {
        pair[x][0]++;
    }
    
    sort(pair.begin(), pair.end(), cmp);
    
    
    for(auto x: pair) {
        k -= x[0];
        answer++;
        
        if(k <= 0)
            break;
    }
    
    return answer;
}

 

나는 벡터의 크기를 문제의 최대 조건에 맞춰서 초기화했는데, 이러면 시간이 다수 걸리긴 한다.

문제 입력에 상관없이 항상 최대까지 벡터를 돌아야 하니까, 테케 당 1초 정도가 요구된다.

통과는 되지만 다소 비효율적이다.

 

 

다른 분의 풀이를 보고 map에다가 넣은 다음에 벡터로 변환하는 방식을 사용하는 방법을 배웠다.

map<int, int> 를 vector<pair<int, int>>로 쉽게 변환할 수가 있다.

map<int, int> m;
vector<pair<int, int>> v(m.begin(), m.end());

 

이를 활용해서 문제를 풀었더니, 더 빠른 시간 안에 통과될 수 있었다.

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

using namespace std;


map<int, int> m;

int cmp(pair<int, int>& a, pair<int, int>& b) {
    return a.second > b.second;
}

int solution(int k, vector<int> tangerine) {
        
    int answer = 0;

    for(auto x: tangerine) {
        m[x]++;
    }
    
    vector<pair<int, int>> v(m.begin(), m.end());
    
    sort(v.begin(), v.end(), cmp);
    
    
    for(auto x: v) {
        k -= x.second;
        answer++;
        
        if(k <= 0)
            break;
    }
    
    return answer;
}