[프로그래머스][C++] 귤 고르기

귤 고르기

문제 링크

귤 고르기

분석

귤이 여러 개 있는데, 각 귤은 특정한 크기를 가집니다.
귤의 크기가 다양할 때, 최소한의 종류만 선택하여 k개 이상을 가져가야 합니다.
이때 필요한 귤의 크기 종류의 최소 개수를 구하는 것이 목표입니다.

unordered_map<int, int>을 사용해 각 귤 크기의 빈도를 저장합니다.
빈도를 vector<int>에 저장하고, 개수를 기준으로 내림차순 정렬합니다.
가장 많이 등장한 크기부터 선택하여 선택한 귤 개수가 k 이상이 될 때까지 귤을 추가합니다.

풀이

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

using namespace std;

int solution(int k, vector<int> tangerine) {
    int answer = 0;
    // 크기별 개수를 저장하는 해시맵
    unordered_map<int, int> countMap;
    
    // 크기별 개수 세기
    for (int e : tangerine)
    {
        ++countMap[e];
    }
    
    // 크기별로 분리된 개수를 벡터로 저장
    vector<int> countVec;
    for (auto e : countMap)
    {
        countVec.push_back(e.second);
    }
    // 개수를 내림차순으로 정렬
    sort(countVec.rbegin(), countVec.rend());

    // 박스에 담은 귤의 개수
    int boxCount = 0;
    // 개수가 가장 많은 크기부터 접근
    for (int i = 0; i < countVec.size(); ++i)
    {
        // 귤 크기의 개수 증가
        ++answer;
        // 박스에 담은 귤 개수 증가
        boxCount += countVec[i];
        
        // 한 상자에 담을 귤의 개수를 채운 경우
        if (boxCount >= k)
        {
            break;
        }
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n log n)$입니다.

• tangerine를 순회해 해시맵 채우기 $O(n)$
• 해시맵에서 벡터로 요소 복사 $O(m)$
• 벡터 정렬 $O(m \ log \ m)$
• 벡터를 순회하는 반복문 $O(m)$
• $O(n + m + m \ log \ m + m) = O(n + 2m + m \ log \ m)$
• $O(n + m log m)

공간 복잡도는 $O(n)$입니다.

• 해시맵을 채울 경우 귤의 크기별로 공간이 필요 $O(n)$
• 해시맵의 요소 복사 $O(n)$
• $O(n)$

테스트 1 〉 통과 (1.36ms, 6.55MB)
테스트 2 〉 통과 (1.60ms, 6.55MB)
테스트 3 〉 통과 (1.15ms, 6.55MB)
테스트 4 〉 통과 (2.38ms, 6.59MB)
테스트 5 〉 통과 (1.36ms, 6.58MB)
테스트 6 〉 통과 (1.32ms, 6.58MB)
테스트 7 〉 통과 (1.69ms, 6.69MB)
테스트 8 〉 통과 (4.71ms, 6.62MB)
테스트 9 〉 통과 (3.77ms, 6.52MB)
테스트 10 〉 통과 (1.96ms, 6.55MB)
테스트 11 〉 통과 (0.02ms, 4.19MB)
테스트 12 〉 통과 (0.01ms, 4.2MB)
테스트 13 〉 통과 (0.01ms, 3.58MB)
테스트 14 〉 통과 (0.01ms, 4.14MB)
테스트 15 〉 통과 (0.01ms, 4.2MB)
테스트 16 〉 통과 (0.01ms, 4.16MB)
테스트 17 〉 통과 (0.01ms, 4.14MB)
테스트 18 〉 통과 (0.01ms, 3.68MB)
테스트 19 〉 통과 (0.01ms, 4.13MB)
테스트 20 〉 통과 (0.01ms, 4.2MB)
테스트 21 〉 통과 (0.05ms, 4.03MB)
테스트 22 〉 통과 (0.09ms, 4.21MB)
테스트 23 〉 통과 (0.11ms, 4.16MB)
테스트 24 〉 통과 (0.13ms, 3.75MB)
테스트 25 〉 통과 (1.40ms, 4.23MB)
테스트 26 〉 통과 (2.78ms, 5.02MB)
테스트 27 〉 통과 (25.37ms, 11.6MB)
테스트 28 〉 통과 (7.34ms, 9.11MB)
테스트 29 〉 통과 (15.12ms, 10.2MB)
테스트 30 〉 통과 (17.28ms, 11.5MB)
테스트 31 〉 통과 (1.00ms, 6.6MB)
테스트 32 〉 통과 (1.44ms, 6.85MB)
테스트 33 〉 통과 (14.45ms, 11.1MB)
테스트 34 〉 통과 (14.05ms, 10.3MB)