경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 '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;
}
'프로그래머스' 카테고리의 다른 글
프로그래머스 lvl 2. 타겟 넘버 [C++] (0) | 2023.08.17 |
---|---|
프로그래머스 lvl 2. 영어 끝말잇기 [C++] (0) | 2023.07.07 |
프로그래머스 lvl 2. 더 맵게 [C++] (0) | 2023.07.04 |
프로그래머스 lvl 2. 전화번호 목록 [C++] (0) | 2023.07.03 |
프로그래머스 lvl 2. 숫자의 표현 [C++] (0) | 2023.07.02 |