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

문제 링크

---

1. 아이디어

귤의 크기가 담긴 배열이 주어질 때 k개의 귤을 고르면서 서로 다른 종류의 수가 최소가 되야하는 문제다. 크기가 같은 귤이 여러 개 존재할 수 있어 해시맵을 활용해 key에 귤의 크기, value에 귤의 개수를 담아 먼저 처리를 해주었다.

이후 해시맵에서 value만 꺼내면 크기 별로 분류된 귤의 개수만 얻을 수 있다. k개의 귤을 선택하면서 귤의 크기 종류가 최소가 되려면 같은 크기에서 귤이 많은 크기의 귤부터 담으면 되므로 value를 역순 정렬한 후 순서대로 담아서 k개 이상 담기려는 순간 종류의 수를 return 해주었다.

---

2. 복잡도

시간복잡도	공간복잡도
$O(N + D\log D)$	$O(D)$

$N$ = tangerine 길이, $D$ = 서로 다른 귤 크기 종류 수(≤ $N$)

---

3. 코드

풀이 [Java][C++]

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;
    }
}

#include <algorithm>
#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> a;
    for (auto [_, v] : mp) {
        a.push_back(v);
    }
    sort(a.rbegin(), a.rend());

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

        if (sum >= k) break;
    }

    return ans;
}

---