[찾아라 프로그래밍 마에스터] 폰켓몬

https://programmers.co.kr/learn/courses/30/lessons/1845

코딩테스트 연습 - 폰켓몬

중복된 원소가 존재할 수 있는 nums 배열 에서 nums.size()/2 개의 원소를 택할 때 최대한

다른 원소를 택할 수 있도록 해야한다.

 

이를 위해서 중복을 허용하지 않는 자료구조인 set 을 이용한다.

set 에 nums 의 원소를 모두 insert 한 뒤,

set 의 크기가 nums.size()/2 보다 작다면 set 의 크기가 답이고

set 의 크기가 nums.size()/2 보다 크다면 nums.size()/2 가 답이다.

 

 

[C++]

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

int solution(vector<int> nums)
{
    int answer = 0;
    int n = nums.size()/2;
    // n 마리의 폰켓몬을 선택해야함.

    set<int> bucket;
    for (int i = 0; i < nums.size(); i++)
    {
        bucket.insert(nums[i]);
    }

    if (bucket.size() > n)
        answer = n;
    else
        answer = bucket.size();
    return answer;
}