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

문제

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

프로그래머스 귤 고르기

 

문제 내용

한 상자에 담으려 하는 귤의 개수 k와, 귤의 크기를 담은 배열 tangerine을 입력받는다.

귤의 개수 k개를 채우되, 귤의 크기의 종류가 최소가 되게 하는 크기의 개수를 구하면 된다.

 

문제 풀이

k개를 채울 때 귤 크기의 종류를 최소화시켜야 할 뿐, 특정 크기의 귤을 모두 사용해서 k개를 채우는 문제가 아니다.

이 부분을 잘못 생각해서 한참을 고민해야 했다.

 

k개를 채울 때 귤 크기의 종류를 최소화시키려면, 귤이 가장 많은 크기부터 사용하면 된다.

그럼 각 크기별로 귤이 몇 개인지를 구해야 한다.

나는 위 내용을 이분 탐색을 사용하여 풀었다. 

upper_bound와 lower_bound를 적절히 잘 조합하면 특정 원소의 개수를 구할 수 있다. (반드시 정렬하고 진행해야 함)

 

위 함수를 통해 귤 크기별 개수를 tangerineSize 벡터에 추가하고, 해당 벡터를 역순으로 정렬한다.

그럼 앞에서부터 귤의 개수를 카운트하면 된다.

 

코드

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

int solution(int k, vector<int> tangerine) {
    sort(tangerine.begin(), tangerine.end());

    vector<int> tangerineSize;
    
    // 크기별로 개수 세기
    int idx = 0;
    while (true) {
        if (idx >= tangerine.size())
            break;
        auto k = upper_bound(tangerine.begin(), tangerine.end(), tangerine[idx]);
        int num = k - lower_bound(tangerine.begin(), tangerine.end(), tangerine[idx]);

        tangerineSize.push_back(num);
        idx = k - tangerine.begin();
    }

    sort(tangerineSize.begin(), tangerineSize.end(), greater<>());
	
    // 개수가 많은 것 부터 선택
    int cnt = 0;
    while (k > 0) {
        k -= tangerineSize[cnt];
        cnt++;
    }

    return cnt;
}