[ALGORITHM] LEVEL2 - 귤 고르기

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

프로그래머스

과정

1. tangerine 배열에 있는 귤의 크기를 맵 혹은 벡터에 담는다.
2. 크기 값은 필요가 없고 해당하는 크기의 귤의 갯수만 중요하다.
3. 만약 맵에 담은 경우 벡터에 담아 second 값을 기준으로 내림차순 정렬을 해준다.
4. k값에서 정렬된 배열의 위부터 값을 빼나가며 0이 될때까지 answer의 값을 1씩 증가시켜준다.
5. k<=0이 되는 경우 탈출한다.

생각해보기

시작할 때 tangerine 배열에 있는 값을 1천만 개의 원소 배열에 체크한 뒤 존재하는 경우만 추가 하여 정렬하는 것과 맵에 담은 뒤 정렬하는 것중 무엇이 빠를까?

int chk[10'000'001] 과 map<int, int>로 체크를 한다.

 

코드 및 수행 시간

map 사용

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

using namespace std;

map<int, int> gulm;
vector<int> gul;
int solution(int k, vector<int> tangerine) {
    int answer = 0;
    int len = tangerine.size();
    
    for(int i=0;i<len;++i){
        gulm[tangerine[i]]++;
    }
    
    for(auto it=gulm.begin();it!=gulm.end();++it){
        gul.push_back(it->second);
    }
    
    sort(gul.begin(),gul.end(),greater<int>());
    
    for(int i=0;i<gul.size();++i){
        k-=gul[i];
        ++answer;
        if(k<=0)
            break;
    }
    
    
    return answer;
}

방문 배열 사용

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

using namespace std;

int chk[10'000'001];
vector<int> gul;
int solution(int k, vector<int> tangerine) {
    int answer = 0;
    int len = tangerine.size();
    
    for(int i=0;i<len;++i){
        ++chk[tangerine[i]];
    }
    
    for(int i=1;i<10'000'001;++i){
        if(chk[i])
            gul.push_back(chk[i]);
    }
    
    sort(gul.begin(),gul.end(),greater<int>());
    
    for(int i=0;i<gul.size();++i){
        k-=gul[i];
        ++answer;
        if(k<=0)
            break;
    }
    
    
    return answer;
}

예상 외로 방문 배열을 사용하는 것이 더 오래 걸린다. tangerine의 길이가 짧아서 그런 것으로 생각 된다.