[프로그래머스] Lv.2 귤 고르기 c++

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

프로그래머스

 

수확한 귤 중 k개를 골라야하며 이때 귤의 크기는 최대한 일정해야한다.

즉, 귤의 크기 종류를 최소화 하면서 k개의 귤을 골라내는것이 목표다.

 

예를 들어, 8개의 귤을 수확했고  수확한 귤의 크기가 다음과 같다.

[1, 3, 2, 5, 4 ,5, 2, 3]

이때, 6개의 귤을 판매하고 싶다면 크기 1과 4를 제외한 [2 ,3 ,2 ,5, 5, 3] 귤을 상자에 담으면 귤의 크기 종류는 [2, 3, 5]로 총 3가지가 되어 최소가 된다.

 

풀이 방법

총 사이즈의 종류는 10,000,000으로 int 배열을 선언하여 수확한 모든 귤을 사이즈에 맞게 저장했다.

그리고 sort함수로 내림차순 정렬을 하여 가장 많은 크기의 귤부터 선택할 수 있도록 했다.

그리고 정렬된 배열을 순회하며 귤을 선택하고, 누적 개수가 k개 이상이 되는 순간 반복을 종료한다.

 

풀이 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int dic[10000001]; //귤 크기별 개수 저장
int sum; //현재까지 선택한 귤의 총 개수
int solution(int k, vector<int> tangerine) {
    int answer = 0; //선택한 귤 크기 종류의 개수
    
    //1. 귤 크기별 개수를 저장
    for(int i=0; i<tangerine.size(); i++){
        dic[tangerine[i]]++;
    }
    
    //2. 개수를 기준으로 내림차순 정렬
    sort(dic, dic+10000001, greater<int>{});
    
    //3. 귤 개수를 k개가 될 때까지 선택
    for(int i=0; i<10000001; i++){
        if(sum >= k) break;
        sum+=dic[i];
        answer++;
    }
    return answer;
}

 

시간복잡도

- 귤 크기별 개수를 저장: O(n)

- 정렬: O(m log m) m은 실제로 존재하는 귤 크기의 종류 수 

- 귤 선택 과정 : O(m)

 

전체 시간복잡도는 O(n + mlongm)