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

 이 문제는 그리디로 풀었다. 문제에서 주어진 배열에서 k개의 귤을 고르는데, 종류가 다른 수를 최소화하는 문제였다. 처음에 배열을 순회하면서 해당 숫자의 cnt를 세고, cnt가 높은 순서로 배열을 정렬한다. 그 다음 k개를 선택하면서 종류가 달라졌을때 answer++을 하면 쉽게 풀 수 있다.

 

 

 

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

using namespace std;

map<int, int> cnt;

bool compare(int a, int b) {
    if (cnt[a] == cnt[b]) {
        return a > b;
    }
    return cnt[a] > cnt[b];
}

int solution(int k, vector<int> tangerine) {
    int answer = 0;
    
    // base case
    if (tangerine.size() == 1) {
        return 1;
    }
    
    for (int t : tangerine) {
        cnt[t]++;
    }
    
    sort(tangerine.begin(), tangerine.end(), compare);
    
    answer = 1;
    int first = tangerine[0];
    k--;
    for (int i = 1; i <= k; i++) {
        if (first != tangerine[i]) {
            first = tangerine[i];
            answer++;
        }
    }
    
    return answer;
}