Programmers / 귤 고르기 / C++

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: 귤 고르기 (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/138476

프로그래머스

 

문제 설명

 

---

 

나의 풀이

 

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

int solution(int k, vector<int> tangerine) {
    int answer = 0;
    vector<int> gul(10000001);
    int i = 0;
    
    for (int i : tangerine) {
        gul[i]++;
    }

    sort(gul.rbegin(), gul.rend());

    while (k > 0) {
        k -= gul[i];
        i++;
        answer += 1;
    }

    return answer;
}

 

풀긴 풀었다. 근데 이 풀이는 시간을 너무 많이 잡아먹어서 다른 풀이 방법을 고안하게 되었다.

 

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

int solution(int k, vector<int> tangerine) {
    int answer = 0;

    map<int, int> m;
    vector<int> v;
    for (int i : tangerine) {
        m[i]++;
    }

    for (pair<int, int> u : m) {
        v.push_back(u.second);
    }

    sort(v.rbegin(), v.rend());

    int cnt = 0;
    for (int i : v)
    {
        if (cnt >= k) break;
        answer++;
        cnt += i;
    }

    return answer;
}

 

map을 이용해서 풀면 시간을 더 단축할 수 있다. 

---

※ 알아야 할 것

 

vector는 데이터를 순차적으로 저장하므로 검색속도가 map, hash_map, set 이들보다 상대적으로 속도가 느리다. 그래서 이런 데이터를 저장해서 검색하는 문제를 풀 때는 map과 hash_map, set을 이용하는 것이 좋다. 그리고 for에서 auto를 사용하면 map의 자료형을 자동으로 바꿔서 바로 사용할 수 있지만 공부를 하는 입장에서는 auto보다 어떤 자료형인지 써주는 것이 더 좋은 것 같다.