프로그래머스 - 귤 고르기(C++)

 이번에도 빡구현문제다. 프로그래머스 구현문제들은 문제를 이해하긴 되게 쉬운데 막상 어떻게 하지? 생각하면 잘 안풀리는게 특징이다.

 

* 문제풀이 *

1. 주어진 귤의 사이즈대로 map에 삽입한다. 

2. 갯수가 큰 순서대로 sort 한다.

3. 1개씩 더하고 k 보다 크거나 같아지면 멈추고 지금까지 넣은 사이즈의 귤의 갯수를 리턴한다.

 

다른 사람들 풀이보니까 짧고 간단하게 했던데.. 봐도 이해도 안가고 모르겠다. 그리고 실행시간을 보니 그닥 좋은 풀이는 아닌 것 같다.

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

bool compare(const int a, const int b){
    return a > b;
}

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

    map<int, int> number;
    for(int i = 0; i < tangerine.size(); i++){
        if(number.empty())
            number.insert(make_pair(tangerine[i], 1));
        else if(number.find(tangerine[i]) != number.end()) // 찾으면
            number[tangerine[i]]++;
        else
            number.insert(make_pair(tangerine[i], 1));
    }
    vector<int> vec;
    for(int i = 0; i < number.size(); i++){
        vec.push_back(number[i]);
    }

    sort(vec.begin(), vec.end(), compare);

    int sum = 0;
    int i = 0;
    while(true){
        sum += vec[i];       
        answer++;

        if(sum > k)
            break;
        else if(sum == k)
            break;
        i++;
    }

    return answer;
}

 

테스트 케이스가 많아서 좀 쫄렸다.