[프로그래머스/level2] 귤 고르기

 

문제

 

 

풀이과정

문제에서 가장 주의해야 할 점은 지금까지 담은 귤의 개수가 k개에 꼭 맞게 담아야 하는 게 아니라, k개 이상일 때의 서로 다른 종류의 수의 최솟값을 찾아야 한다는 것이다.

입출력 예 #1에 나온 것처럼 k가 6일 때, 넣을 귤의 개수를 딱 6개로 맞춰야 할 필요가 없고 개수가 k개를 넘어가되 종류의

수가 최소이기만 하면 된다. 

 

입출력 예 #1로 더 자세하게 설명하면,
tangerine = [1, 3, 2, 5, 4, 5, 2, 3] 일 때 수확한 귤 8개 중, 크기가 2인 귤 2개 + 크기가 3인 귤 2개 + 크기가 5인 귤 2개 = 6개 = k (귤 종류는 3가지로 정답)

tangerine = [1, 3, 2, 5, 5, 4, 5, 2, 3] 일 때 수확한 귤 9개 중, 크기가 2인 귤 2개 + 크기가 3인 귤 2개 + 크기가 5인 귤 3개 = 7개 > k (귤 종류는 3가지로 정답)

 

즉, 넣을 귤의 합 >= k가 되는 귤 종류의 최솟값을 구하면 된다.

 

처음 문제를 풀 때 map으로 접근하려고 했으나 종류의 값을 반환할 필요가 없고 가짓수의 최솟값만 리턴하면 되므로 1차원 벡터를 사용하였다. (종류를 가지고 있을 필요가 없음)

 

넣을 귤의 합 >= k가 되는 귤 종류의 최솟값은 무조건 개수가 많은 순부터 차례대로 더하면 되므로 쉽게 구할 수 있다.

 

 

풀이 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(int k, vector<int> tangerine) {
    int answer = 0;
    
    // 종류 index 저장하기 - tangerine에 들어있는 최대값까지 0으로 push_back
    // countVector에서의  index: n 크기 종류    element: 해당 크기의 귤 개수    =>   0번째 요소가 2 = 크기가 1인 귤이 2개 있음
    vector<int> countVector(*max_element(tangerine.begin(), tangerine.end()), 0);
    
    for (int i = 0; i < tangerine.size(); i++)
        countVector[tangerine[i] - 1]++; // 돌면서 해당 값 index에 + 1
    
    // countVector에 넣은 요소들 중 가장 큰 수부터 차례대로 더하기
    sort(countVector.rbegin(), countVector.rend());
    
    int sum = 0;
    for (int i = 0; i < countVector.size(); i++) {
        sum += countVector[i];
        answer++;
        if (sum >= k) break;
    }
    
    return answer;
}

 

 

실행 결과