코딩 테스트 -- 귤 고르기 - (프로그래머스 / C++)

프로그래머스

 

문제!

---

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.

예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.

경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

---

요약하면 최소한의 귤 종류로 갯수를 맞춰 담을때 종류의 최소값을 구하는 문제!

 

문제 자체는 어렵지 않습니다. 

하지만 벡터로 풀기에는.. 

• 1 ≤ tangerine의 원소 ≤ 10,000,000

귤의 종류가 천만개정도 될수 있어 나중에 정렬 할 경우 문제가 생길수 있습니다.

 

그래서 저는 map을 사용해서 풀어 보았습니다!

 

 

시작!

---

가장 먼저 귤의 종류별 갯수를 저장해줄 map을 선언해주고

map<int, int> save;

 

map에서 찾아 값을 넣어주거나 새로 추가해줍시다.

for(int i : tangerine){//ck찾기
        if (save.find(i) != save.end()) {
            save[i]+=1;
        }
        else {
            save.insert(pair<int, int>(i, 1));
        }
    }

 

그다음 정렬을 위해 벡터에 넣어줍시다. (다른방법이 있을수도 있지만 전 이 방법이 제일 쉽네요!)

 

 vector<pair<int,int>> all_list(save.begin(), save.end());

 

그리고 정렬을 위한 함수를 만들어 주고

bool cmp(const pair<int,int>& a, const pair<int,int>& b) {
	if (a.second == b.second) return a.first > b.first;
	return a.second > b.second;
}

 

정렬!

sort(all_list.begin(),all_list.end(),cmp);

 

 

그리고 마무리로 갯수가 많은 부분부터 선택한다고 생각하고  k가 0이하가 될때 까지 반복하여 뽑아주면 끝!

int sel_index=0;
    
    while(k>0){
        if(k<=all_list[sel_index].second){
            answer+=1;
            break;
        }
        else{
            answer+=1;
            k-=all_list[sel_index].second;
        }
        sel_index+=1;
    }

 

 

ALL

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

bool cmp(const pair<int,int>& a, const pair<int,int>& b) {
	if (a.second == b.second) return a.first > b.first;
	return a.second > b.second;
}



int solution(int k, vector<int> tangerine) {
    int answer = 0;
    
    // map 쓰기 갯수 저장해서 현재 갯수보다 작거나 같은 과일 계속 채용 
    
    // 찾는걸 어케 >> 정렬?
   map<int, int> save;

    for(int i : tangerine){//ck찾기
        if (save.find(i) != save.end()) {
            save[i]+=1;
        }
        else {
            save.insert(pair<int, int>(i, 1));
        }
    }
    
    vector<pair<int,int>> all_list(save.begin(), save.end());
    
    sort(all_list.begin(),all_list.end(),cmp);
    
    
    int sel_index=0;
    
    while(k>0){
        if(k<=all_list[sel_index].second){
            answer+=1;
            break;
        }
        else{
            answer+=1;
            k-=all_list[sel_index].second;
        }
        sel_index+=1;
    }
    
    
    return answer;
}

 

 

 

틀린점이 있다면 댓 달아주세요!