문제 풀이 과정을 공유하고자 한다.
문제 출처

1. 문제설명

• 수확한 귤 중 k개를 골라 하나의 상자에 담으려고 한다.
• 귤의 크기가 일정하게 담고 싶다.
  • 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶다.
• 귤의 개수 k, 귤의 크기를 담은 배열 tangerine이 주어진다.
  • 1 <= k <= tanngerine의 길이 <= 100,000
  • 1 <= tanngerine의 원소 <= 100,000

2. 알고리즘 설계

• 각 원소의 개수 카운팅
• 개수를 큰 순서에 따라 정렬
• 개수를 임시 변수에 더해주면서 k값 보다 작을 때까지 더해준다.
  • 더할 때마다 경우의 수를 1씩 추가한다.

3. 로직

• 원소는 1 ~ 10,000,000 중 하나이다.
  • 각 원소의 개수를 카운팅하기 위해 map 구조를 사용한다.
  • 배열을 사용하는 방법도 있지만, 크기만큼 선언해야 되서 비효율적이다.
• 카운팅을 vector에 담는다.
• 벡터를 큰 순서가 앞에 오도록 정렬한다.
  • sort()는 오름차순이 default이다.
  • bitwise-not 이용
    • 관련 포스팅
• 벡터의 첫 원소부터 k보다 작을 때까지 더한다.

4. 전체 코드

#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int solution(int k, vector<int> tangerine) 
{
    map<int, int> m;
    for(int t : tangerine) m[t]++;
    
    vector<int> v;
    for(auto u : m)
        v.push_back(~u.second);
    
    sort(v.begin(), v.end());
    
    int answer=0, cnt=0;
    for(int i : v) {
        if (cnt >= k) break;
        answer++;
        cnt += ~i;
    }
    
    return answer;
}

5. 소감

• bitwise-not 매우 잘 쓰고 있다.
• 사실 처음에 배열로 구현했다가, 매우 비효율적인 거 같아 정답을 보았다.
  • map 사용에 익숙해져야겠다.