[ 프로그래머스 C++ ] 귤 고르기 lv2

< 해설 >

가장 적은 종류로 원하는 귤의 개수를 채워야 하는 문제이다. 귤의 크기별로 개수를 모아주고 정렬하면 쉬운 문제. 귤의 크기가 인접해야 한다거나 하는 조건은 없으니 잘 읽자. (이래서 혼자 조금 헤맸다.)

예시가 10'000'00  까지 있지만 특정 자료구조를 사용하지 않으면 시간초과가 나거나 하는 문제는 아니었다.

다만 귤의 개수보다 요구하는 k의 개수가 더 클 때 예외 처리는 필요하다.

 

코딩테스트 처음 할 때 풀려고 흔적만 남겨뒀던 문제인데 지금와서 다시 푸니 감회가 새롭다.

당분간은 2단계 풀면서 코딩테스트에 다시 정 붙여야할것 같음 ㅠㅠ 3단계 너무 하기싫어~

 

< 문제 >

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.

예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.

경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

< 풀이 >

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int k, vector<int> tangerine) {
    int answer = 0; 
    vector<int> vecTanger(10'000'001);

    for (int i = 0; i < tangerine.size(); i++)
    {
        vecTanger[tangerine[i]] += 1;
    }

    sort(vecTanger.begin(), vecTanger.end(), greater<int>());

    while (true)
    {
        if (k <= 0)
            break;
        else
        {
            if(vecTanger[answer] == 0)
                return answer;
            k -= vecTanger[answer];
            answer++;
        }
    }
    return answer;
}