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

 

 

 

 

 

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;
}

 

프로그래머스 - 결과 화면