폰켓몬 C++

문제 설명

제한사항

• nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.
• nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.
• 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.
• 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.

---

입출력 예

nums                                                                                                                                                       result

[3,1,2,3]	2
[3,3,3,2,2,4]	3
[3,3,3,2,2,2]	2

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다.
가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리, 2번 폰켓몬 한 마리, 4번 폰켓몬 한 마리를 고르면 되며, 따라서 3을 return 합니다.

입출력 예 #3
6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다.
가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리와 2번 폰켓몬 두 마리를 고르거나, 혹은 3번 폰켓몬 두 마리와 2번 폰켓몬 한 마리를 고르면 됩니다. 따라서 최대 고를 수 있는 폰켓몬 종류의 수는 2입니다.

 

#include <vector>
#include <set>
#include <algorithm>
using namespace std;



int solution(vector<int> nums)
{
    int answer = 0;
    int N = nums.size();
    set<int> s; 
    for(auto number : nums)
    {
        s.insert(number); //set은 중복된 숫자가 들어가지 않음
    }
    
    if(s.size() >= N/2)
    {
        answer = N/2;
    }
    else answer = s.size();
    
    return answer;
}

 

 

=> 처음에는 순열을 이용해 풀려고 했으나 , 수학적으로 간단하게 풀 수 있는 문제입니다. 

=> 폰켓몬을 최대한 잡을 수 있는 경우의수는 N/2입니다.  => 즉, 폰켓몬의 종류가 N/2보다 클 경우 무조건 최대의 경우의 수는 N/2입니다. 

=> 또한 N/2보다 폰켓몬의 종류가 낮을 경우 역시 최대의 경우의 수는 폰켓몬의 종류입니다. 

=> set은 중복된 key값 원소들의 집합입니다. (즉, 원소의 중복을 허용하지 않습니다. )

=> set Contatiner에 관해서는 추후 정리해두도록 하겠습니다.