[프로그래머스] 프로그래머스 Level1 폰켓몬 C++

문제

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

코딩테스트 연습 - 폰켓몬

풀이

문제를 풀기위한 알고리즘은 따로 필요 없었고, 오히려 쉽게 생각해야 금방 풀 수 있는 문제이다.

필자는 처음에 백트래킹으로 접근하려했지만 생각해보니 자료구조인 Set을 사용하면 금방 풀 수 있을 거 같아서 Set을 통해 해결할 수 있었다.

Set에 모든 nums의 원소들을 담아주면 중복 없는(종류가 모두 다른) 값들만 얻을 수 있고 이후 Set의 크기를 측정한다 이때 분기가 2개로 나뉘는데

i) Set의 크기가 가질 수 있는 최대 폰켓몬 수보다 크거나 같을때 => 서로 다른 종류의 폰켓몬들이 최대 폰켓몬 수보다 같거나 크므로 모두가 서로 다른 종류의 폰켓몬을 가진 조합이 나올 수 있기는 것이다. 즉, 우리가 가질 수 있는 최대 폰켓몬 종류의 수인 num/2를 리턴해주면 된다.

ii) Set의 크기가 가질 수 있는 최대 폰켓몬 수보다 작을때 => 아무리 선택을 잘한다해도 애초에 폰켓몬의 종류가 가질 수 있는 최대 폰켓몬 종류의 수 보다 적으므로 폰켓몬 종류의 수를 리턴해주면 된다.

코드

#include <vector>
#include <set>

using namespace std;

int solution(vector<int> nums)
{
    int pivot = nums.size() / 2;

    set<int> pocket;

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

    if (pocket.size() >= pivot)
    {
        return pivot;
    }
    else
    {
        return pocket.size();
    }
}