[PS] 귤 고르기

문제

해결

생각보다 시간을 많이 쓴 문제였는데, 괜히 DP나 greedy 풀이법을 고민하느라였다.
이 문제는 한 가지 사항을 주의해야하는데, 바로 크기가 동일한 귤의 '일부'를 담을 수 있다는 것이다.
예를 들어 아래와 같이 귤이 있고, k가 10이라고 친다면

1
2
3
4
5 5 5 5 5
6 6 6 6 6
7 7 7 7 7 7

이러면 7 6개 6 4개 또는 6 5개 5 5개 넣으면 끝이다.

나는 해당 크기의 귤을 전부 담아야 한다고 착각해서 불필요하게 시간을 오래 소모했다. 사실 입출력예시 3번만 제대로 봤어도 금방 풀 수 잇을만한 문제였는데.

여튼 풀이법은, pair(원소, 원소 개수) 배열을 하나 만들고, 원소 개수가 큰 순서대로 내림차순 정렬하고 그 배열을 0번부터 순회하면서 k -= 원소 개수; answer++(원소 종류 추가) 하다가 k가 0보다 작거나 같아지는 시점에 반환을 하면 된다.

코드

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

#define pii pair<int,int>

using namespace std;
int solution(int k, vector<int> t) {
    int answer = 0;
    vector<pii> v;
    sort(t.begin(), t.end());
    int lastElem = 0;
    for(int elem : t)
    {
        if(lastElem != elem)
        {
            v.push_back(make_pair(elem, 1));
            lastElem = elem;
        }
        else
        {
            v[v.size() - 1].second++;
        }
    }
    sort(v.begin(), v.end(), [](const pii& a, const pii& b){
       return a.second > b.second;
    });
    for(pii elem : v)
    {
        k -= elem.second;
        answer++;
        if(k <= 0) break;
    }
    return answer;
}

교훈: 문제의 조건을 똑바로 읽자