[Programmers_C++]#Level2_귤 고르기, map, priority_queue, 우선순위 큐

 

#1. 문제

 

 

---

#2. 풀이

 

1. map 컨테이너

[Basic C++] #38_map, 연관 컨테이너

 

Details

 

map 컨테이너는 C++ STL에서 제공하는 연관 컨테이너로, 키와 값을 한 쌍으로 레드-블랙 트리 자료구조에 저장합니다.

 

2. 우선순위 큐

[자료구조]#7_우선순위 큐

 

Details

 

priority_queue 컨테이너는 힙 자료구조를 활용해 각 항목에 우선순위를 부여하고, 우선순위를 기준으로 내부적으로 반 정렬된 상태를 유지합니다. priority_queue 컨테이너의 디폴트 정렬 기준은 최대 힙(less)이며, 변경이 가능합니다.

 

3. map으로 사이즈별 귤 개수 세고, 우선순위 큐로 사이즈 종류 세자

1. 먼저, pair<int, int> 형식으로 귤의 사이즈와 개수를 세고, map 컨테이너에 저장
2. 다음으로, map 컨테이너를 순회하며 각 사이즈 별 귤 개수를 pq(우선순위 큐)에 삽입합니다.
3. 우선순위 큐의 top 항목을 pop 하고, k에서 해당 항목을 차감합니다.
4. k가 0이하가 될 때까지, 위 작업을 반복합니다. 최종적으로, 최소 귤의 종류는 pq에서 pop 한 항목의 개수가 됩니다!

 

---

 

#3. 코드

#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

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

    // #1. map을 통해 크기 별 귤의 개수를 구한다.
    map<int, int> m;
    for (int i = 0; i < (int)tangerine.size(); ++i)
        m[tangerine[i]]++;

    // #2. 우선순위 큐에 크기 별 개수를 삽입한다.
    priority_queue<int> pq;
    for (auto it = begin(m); it != end(m); ++it)
        pq.push(it->second);

    // #3. 우선순위 큐의 top을 꺼내며, k개수를 차감하며 0이하가 될때 까지 종류를 카운트한다.
    while (!pq.empty())
    {
        int num = pq.top();
        pq.pop();

        answer++;
        k -= num;
        if (k <= 0)
            break;
    }

    return answer;
}

 

---