[프로그래머스] 귤 고르기 C++ 풀이

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

프로그래머스

 

전체 코드

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;

int solution(int k, vector<int> tangerine) {
    int answer = 0;
    map<int, int> m;
    map<int, int>::iterator it;
    
    // map에 각 귤의 크기에 따른 개수를 저장.
    for(int i=0; i<tangerine.size(); i++){
        it = m.find(tangerine[i]);
        if(it==m.end())
            m.insert({tangerine[i], 1});
        else
            it->second++;
    }
    
    /*
    vector<pair<int, int>> v(m.begin(), m.end()); 
    이렇게 map에서 키와 값을 모두 vector에 넣으면 정렬시 11번 테케에서 (signal: aborted (core dumped))발생.
    */
    
    
    // (크기별)귤의 개수들을 저장
    vector<int> v;
    for(it=m.begin(); it!=m.end() ;it++){
        v.push_back(it->second);
    }
        
    // 귤의 개수를 내림차순으로 정렬
    sort(v.begin(), v.end(), greater<>());
    
    // 귤의 개수를 빼가며 0이하가 되는 순간을 잡음
    for(int i=0; i<v.size(); i++){
        k-=v[i];
        answer++;
        if(k<=0)
            break;
    }
    return answer;
}

풀이 방법

우리는 k개의 귤을 최대한 종류가 같개 뽑아야 한다.

그러므로 종류가 같은개 많은 귤들을 먼저 뽑아가며 k개를 맞추면 최소한으로 서로 다른 종류를 가질 수 있다.

 

    for(int i=0; i<v.size(); i++){
        k-=v[i];
        answer++;
        if(k<=0)
            break;
    }

귤 종류가 많은 개수대로 정렬되어있다.

여기서 귤의 개수를 빼가며 뺸만큼 K에서 뺀다.

그럼 K가 0이하가 되는 순간이 우리가 뽑아야할 K개를 뽑은 상태가 된다.