프로그래머스 lvl 2. 귤 고르기 [C++]

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류 했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소 일 때 입니다.경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine 이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

접근 point

• unordered_map
• 내림차순 정렬

가장 많은 귤을 가지고 있는 크기부터 고를 때, 서로 다른 종류의 수의 최솟값을 구할 수 있다.

 

 

Pseudocode 

1. unordered_map에 귤 크기(key)에 따른 개수(value)를 저장

2. unordered_map을 vector<pair<int,int>>로 변환 후 value값을 기준으로 내림차순 정렬

3. k개의 귤을 다 고를 때 까지 vector 배열에서 가져온 귤 개수만큼 빼고 종류의 수 올리기

 

 

#include <bits/stdc++.h>
using namespace std;

unordered_map<int,int> m;

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

int solution(int k, vector<int> tangerine) {
    int cnt = 0;
    for(int i = 0; i < tangerine.size(); i++) {
        m[tangerine[i]]++; // 귤 크기에 따라 개수 저장
    }
    vector<pair<int,int>> vec(m.begin(), m.end());
    sort(vec.begin(), vec.end(), cmp); // 귤 개수를 기준으로 내림차순 정렬
    
    for(int i = 0; i < vec.size(); i++) {
        if(k > 0) { // k개 귤만큼 고르기
            k -= vec[i].second; // k에서 귤 개수 제거
            cnt++; // 귤 종류 증가
        } else {
            break;
        }
    }
    return cnt;
}