[프로그래머스/Level 2/C++/연습문제] 귤 고르기

https://school.programmers.co.kr/learn/courses/30/lessons/138476

- 출처 : 프로그래머스 코딩 테스트 연습

프로그래머스

 

[문제 요약]

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

 

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

 

- 경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수를 구하시오.

 

[문제 조건]

• 1 ≤ k ≤ tangerine의 길이 ≤ 100,000
• 1 ≤ tangerine의 원소 ≤ 10,000,000

[문제 풀이]

문제가 원하는 바는 아주 간단하다. k개 만큼 귤을 고르는데 골랐을 때 귤의 크기의 종류가 최소가 되게 고르면 된다.

 

귤의 크기의 종류가 최소가 되려면 갯수가 많은 크기의 귤부터 차례대로 넣어주면 자연스레 종류가 최소가 되게 선택이 된다. 따라서 어떤 크기의 귤들을 넣어야지 최소가 되는지는 중요하지 않고 개수만 중요하기 때문에 개수에 초점을 맞춰서 문제를 풀었다.

 

처음에 주어지는 배열 tangerine을 오름차순으로 배열한다음, 처음부터 확인하면서 같은 크기의 귤들이 각각 몇 개인지 세어서 cntinfo라는 배열을 만들어 종류별 개수를 저장하였다.

 

그다음 cntinfo 배열을 다시 내림차순으로 정렬한 뒤 처음원소부터 차례대로 k가 0보다 큰 동안 k에서 원소 값을 빼주면서 answer를 하나씩 증가시켜주면 그게 정답이 될 것이다.

 

[소스 코드]

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

using namespace std;

bool cmp(int &a, int &b)
{
    return a>b;
}

int solution(int k, vector<int> tangerine) {
    int answer = 0;
    int n = tangerine.size();
    vector<int> cntinfo;
    
    sort(tangerine.begin(), tangerine.end());
    tangerine.push_back(0);
    
    int cnt = 0;
    for(int i=0; i<n; i++)
    {
        if(tangerine[i] == tangerine[i+1]) cnt++;    
        else 
        {
            cnt++;
            cntinfo.push_back(cnt);
            cnt=0;
        } 
    }
    
    sort(cntinfo.begin(), cntinfo.end(), cmp);
   
    for(int i=0; i<cntinfo.size(); i++)
    {
        if(k>0)
        {
            k=k-cntinfo[i];
            answer++;
        }
    }
    
    return answer;
}

굳