programmers [C++] : 폰켓몬

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

코딩테스트 연습 - 폰켓몬

문제 설명

---

총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.
홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다.

예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 6가지가 있습니다.

 

첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다.
최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 할때 얻을 수 있는 최대의 폰켓몬 종류의 수를 구하시오. 

 

접근 방법

---

생각보다 쉽게 접근할 수 있습니다. ^^

가장 많은 종류를 얻으려는 것이므로 중복을 제거하고 시작하시면 됩니다. 그러면 두가지의 경우의 수만 남게됩니다.

 

1-1. 중복을 제거했을때 총 사이즈가 N/2보다 작다면 어떻게 선택을 하더라도 총사이즈 만큼의 개수가 나오게 됩니다.

1-2. 만일 사이즈가 N/2보다 크다면 선택할 수 있는 최대 개수인 N/2로 수렴하게 됩니다. 

 

이렇게 되면 중복제거와 조건문 두개로 문제를 풀 수 있습니다!

 

코드

---

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

int solution(vector<int> nums)
{
    int range=nums.size()/2;
    
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    int range2=nums.size();
    if(range>=range2)return range2;
    else return range;
}

funny algorithm 0_<