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

문제 설명

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.

예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.

경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한 사항

• 1 ≤ k ≤ tangerine의 길이 ≤ 100,000
• 1 ≤ tangerine의 원소 ≤ 10,000,000

입출력 예

k	tangerine
6	[1, 3, 2, 5, 4, 5, 2, 3]	3
4	[1, 3, 2, 5, 4, 5, 2, 3]	2
2	[1, 1, 1, 1, 2, 2, 2, 3]	1

풀이

각 종류별로 귤의 개수를 파악하기 위해 map 자료구조를 사용하였다.

map은 <key, value> 쌍으로 저장되고, key를 기준으로 오름차순으로 정렬되어 저장된다.

k개수를 충족하기 위한 귤 종류의 최소를 구하기 위해서

value 기준으로 내림차순으로 정렬하도록 코드를 구현하였다.

1. sort 함수는 vector자료구조에 있는 함수로 map데이터를 vector에 옮긴다.

2. custorm compare 함수를 만들어 value기준으로 내림차순으로 정렬한다.

3. 반복문으로 vector의 second 원소가 k 이상인지 검사한다.

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

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> hash;
    for(const auto& it : tangerine){
        hash[it] += 1;
    }
    
    vector<pair<int, int>> vec (hash.begin(), hash.end());
    
    sort(vec.begin(), vec.end(), cmp);
    
    int tmp = k;
    for(const auto& it: vec){
        answer++;
        if(it.second < tmp){
            tmp -= it.second;
        }
        else{
            break;
        }
    }
    
    return answer;
}

 

다른 풀이

1. max_element함수를 사용하여 tangerine의 최대 원소를 구한다.

    귤의 종류는 1~m 가지이다.

2. 귤 종류에 따른 개수를 구한다.

3. 내림차순으로 정렬하기 위해 reverse begin, end 반복자를 매개변수로 지정한다.

4. 정렬된 vector의 원소가 k개 이상인지 검사한다.  

using namespace std;

int solution(int k, vector<int> tangerine) {
    int answer = 0;
    int m = *max_element(tangerine.begin(), tangerine.end());
    vector<int> v(m, 0);
    for(auto& t : tangerine){
        v[t - 1]++;
    }
    stable_sort(v.rbegin(), v.rend());
    for(int i = 0 ; i < v.size() ; i++){
        answer++;
        k -= v[i];
        if(k <= 0) return answer;
    }
    return answer;
}