[Programmers] 귤 고르기

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

프로그래머스

 

---

 

문제 해결 과정

착안

각각 크기 별로 귤을 분류하여 저장할 배열을 만들어, 같은 크기의 귤마다 몇 개씩 있는지를 파악한 다음 배열을 내림차순으로 정렬하면 탐욕 알고리즘에 기반하여 문제를 쉽게 해결할 수 있다.

 

구현

std::unordered_map<> 클래스를 활용하면 귤을 크기 별로 몇 개씩 있는지 쉽게 파악할 수 있다. 이때 std::sort() 메서드를 사용해 정렬하기 위해서는 std::unordered_map<> 클래스에 저장한 데이터를 std::vector<pair<>> 형식으로 변경해야한다.

 

크기별로 나뉜 귤을, 가장 많은 수가 존재하는 크기부터 내림차순으로 정렬하고 나면 문제에서 목표로 하는 $k$ 개의 귤을 선택할 때까지 수가 많은 크기부터 귤을 선택하면서 귤의 크기 종류를 나타내는 수를 1씩 증가시켜 문제를 해결하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

int solution(int k, vector<int> tangerine)
{
    unordered_map<int, int> partition;
    
    for (int n : tangerine)
        partition[n]++;
    
    vector<pair<int, int>> sorted(partition.begin(), partition.end());
    sort(sorted.begin(),
         sorted.end(),
         [](const pair<int, int>& a, const pair<int, int>& b)
         {
             return a.second > b.second;
         });
    
    int sum = 0, answer = 0;
    for (pair<int, int> p : sorted)
    {
        sum += p.second;
        answer++;
        if (sum >= k)
            break;
    }
    
    return answer;
}

 

실행 결과