[프로그래머스] 2단계 - 귤 고르기

문제 설명

수확한 귤 중 k개를 골라 한 상자에 담아 판매하려고 할 때, 서로 다른 종류의 귤의 수의 최솟값을 return

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

프로그래머스

 

문제 풀이법

vector와 sort를 사용하면 금방 풀 수 있다

 

서로 다른 종류의 수를 최소화 하기 위해서는 공통인 수를 먼저 가져가야 한다

수가 중복인 것을 알기 위해서 주어진 tangerine을 순회하면서 vector에 해당 인덱스에 + 1을 하면서 각 원소들을 count 한다

vector를 내림차순하여, 순회를 하며 귤을 k개만큼 담기 시작한다

 

이때 cnt는 총 담은 귤의 수이고, answer은 담은 귤의 종류이다

vector를 내림차순 했으니, 가장 수가 많은 귤부터 담길 것이다

예시로 [1, 3, 2, 5, 4, 5, 2, 3]이 있는 귤은 1이 1개, 2가 2개, 3이 2개, 4가 1개 5가 2개이므로 2, 3, 5가 가장 먼저 담길 것이다

 

귤을 담을때는 2개 이상일때만 먼저 담는다

귤을 담으면서 한 상자에 담으려는 귤의 개수 k개를 넘지 않는지 확인한다

담으려는 귤의 수가 k개를 넘으려 하면 딱 k개 만큼만 담도록 한다

 

만일 cnt == k 라면, 한 상자에 담으려는 귤의 개수가 다 찬 것이므로 바로 answer을 return 해준다 

for문을 끝내고 나오면 아직 귤을 다 담지 못한 상태일 것이다

이때는 이제 중복된 크기의 귤은 다 담은 것이므로 나머지는 1개짜리인 귤 뿐이니 answer에 남은 귤의 수를 더해주고 return 한다

 

소스 코드

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

using namespace std;

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

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