[Programmers] 138476번 - 귤 고르기 [Java][C++]

문제 링크

---

1. 문제 풀이

$k$ 개의 귤을 담아야 하는데 이때 귤의 종류의 수를 최소화해야 하는 문제다. 맵 자료구조를 활용해서 크기별 개수를 구한 후 개수가 많은 귤 종류부터 담으면 최소 종류로 $k$ 개를 담을 수 있다.

---

2. 코드

1. 풀이 [Java]

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int t : tangerine) {
            map.put(t, map.getOrDefault(t, 0) + 1);
        }

        List<Integer> list = new ArrayList<>(map.values());
        list.sort(Comparator.reverseOrder());

        int sum = 0;
        int ans = 0;
        for (int v : list) {
            sum += v;
            ans++;

            if (sum >= k) break;
        }

        return ans;
    }
}

2. 풀이 [C++]

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

using namespace std;

int solution(int k, vector<int> tangerine) {
    unordered_map<int, int> mp;
    for (int t : tangerine) {
        mp[t]++;
    }

    vector<int> v;
    for (auto& [key, value] : mp) {
        v.push_back(value);
    }
    sort(v.rbegin(), v.rend());

    int sum = 0;
    int ans = 0;
    for (int x : v) {
        sum += x;
        ans++;

        if (sum >= k) break;
    }

    return ans;
}

---