[programmers] 귤 고르기

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

프로그래머스

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

크기 별로 tangerine의 개수를 구해, 각 개수를 내림차순 정렬 후, 앞에서부터 더해가며 합이 k개가 되면 종료.

몇 개의 종류를 포함했는지 즉, 앞에서부터 확인한 개수가 정답이다.

 

---------------------------------------------------풀이----------------------------------------------------

 

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

using namespace std;

// 각 크기 별 개수
int sizes[10'000'001] = {0, };
// 개수들을 저장
vector<int> v;

// k개를 골라 서로 다른 종류가 최소가 될 때 그 값=?
int solution(int k, vector<int> tangerine) {
    int answer = 0;
    for(int i = 0; i < tangerine.size(); i++){
        sizes[tangerine[i]]++;
    }
    for(int i = 0; i < 10'000'001; i++){
        if(sizes[i] > 0){
            v.push_back(sizes[i]);
        }
    }
    // 각 개수들을 내림차순 정렬
    sort(v.begin(), v.end(), greater<>());
    
    int sum = 0;
    for(int i = 0; i < v.size(); i++){
        sum += v[i];
        answer++;
        // k개만큼 모두 담았으면 종료
        if(sum >= k){
            break;
        }
    }
    
    return answer;
}

 

---------------------------------------------------후기----------------------------------------------------

 

map을 사용해 각 크기 별 개수를 구하는 방법도 생각했지만, 제일 단순한 방식으로 풀어봤다.

이렇게 풀었더니 테스트케이스의 시간이 거의 14ms로 전부 비슷하게 나왔다.