알고리즘/프로그래머스
[프로그래머스] 귤 고르기 C++ (Lv.2)
lheunoia
2023. 4. 18. 15:24
https://school.programmers.co.kr/learn/courses/30/lessons/138476
이번 문제는 구현 문제였습니다.
📝 문제 풀이
1. kind 벡터에 귤의 종류의 개수를 카운트
2. 서로 다른 종류가 최소가 되도록 귤을 담아야 하므로 kind 벡터를 내림차순 정렬 (종류가 많은 귤부터 담기 위해)
3. kind 벡터의 귤을 순서대로 담다가 현재 담아야 할 귤의 개수가 k 크거나 같아지면 for문 종료
👩🏻💻 C++ 코드
#include <string>
#include <vector>
#include <algorithm>
#define MAX 10000001
using namespace std;
bool cmp(int &a, int &b) {
return a > b;
}
int solution(int k, vector<int> tangerine) {
int answer = 0;
vector<int> kind(MAX); // 각 귤의 종류의 개수를 담은 벡터
// 각 귤의 종류의 개수 세기
for (int t: tangerine) {
kind[t]++;
}
// 종류가 많은 귤부터 담기 위해 내림차순 정렬
sort(kind.begin(), kind.end(), cmp);
for (int i=0; i<kind.size(); i++) {
if (kind[i] < k) {
answer++; // 담은 귤의 종류 개수
k -= kind[i]; // 담은 귤 개수
} else if (kind[i] >= k) {
answer++;
break;
}
}
return answer;
}
반응형