[프로그래머스 / 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

• 벡터의 내림차순 정렬을 위해 sort() 함수를 사용할 것 이므로 algorithm 헤더를 포함
• 경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수를 저장할 정수형 변수 answer을 0으로, 귤의 크기별 개수를 저장할 정수형 벡터 check를 10,000,001의 크기로 0으로 초기화. for loop를 통해 tangerine의 첫번째부터 마지막 원소까지 순환하고, check의 현재 인덱스 원소를 1씩 늘림. loop 탈출 후, sort() 함수를 사용하여 check를 내림차순으로 정렬. 이후, check의 첫번째부터 마지막 원소까지 순환하고, 순환할 때 마다 answer을 1씩 늘림. k에 check의 현재 인덱스 원소를 빼고 저장하고 k가 0이하인 경우 loop 탈출. 최종적으로 저장된 answer을 return

algorithm 헤더의 sort() 함수 사용법
void sort(T start, T end, Compare comp); //comp 인자가 공란이면 오름차순 정렬

• sort(v.begin(), v.end(), compare); // 사용자 정의 함수 사용
• sort(v.rbegin(), v.rend()); // 내림차순
• sort(v.begin(), v.end(), greater<자료형>()); // 내림차순
• sort(v.begin(), v.end(), less<자료형>()); // 오름차순

풀이

#include <vector>
#include <algorithm>

using namespace std;

int solution(int k, vector<int> tangerine) {
    int answer = 0;
    vector<int> check(10000001, 0);
    
    for(int i = 0; i < tangerine.size(); ++i) {
        check[tangerine[i]]++;
    }
    sort(check.rbegin(), check.rend());
    for(int i = 0; i < check.size(); ++i) {
        answer++;
        k -= check[i];
        if(k <= 0) break;
    }
    return answer;
}