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

 

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

vector<int> value;
map<int, int> species_cnt;
int maxx = 0;
int answer = 0;

void dfs(int index, int level){
    if( level == value.size()/2){
        answer = 0;
        for( auto j = species_cnt.begin(); j!=species_cnt.end(); j++){
            if(j->second != 0 ) answer += 1;
        }
        maxx = maxx > answer ? maxx : answer;
    }
    else{
        for(int i = index; i<value.size(); i++){
            species_cnt[value[i]] += 1;
            dfs(i+1, level+1);
            species_cnt[value[i]] -= 1;
        }
    }
}

int solution(vector<int> nums)
{
    value = nums;
    dfs(0, 0);
	return maxx;
}

처음엔 이렇게 풀었다. DFS로 N/2개를 갖는 부분집합을 구하고 map으로 종류에 따른 개수를 확인했다.

그런데 테스트 케이스 몇개는 통과하는데 엄청난 시간초과가 발생한다. 

 

 

 

다른 사람들의 풀이를 봤다.

이거는 진짜로 하나하나 다 확인하면서 푸는 그런 문제가 아니였다. 

어차피 폰켓몬의 종류만 생각하면 되는 것이므로 unique 함수로 중복되는 원소를 뽑아내고 erase 함수로 그 원소를 삭제한다.

중복을 제거한 벡터 nums 의 크기는 폰켓몬이 가지고 있는 종류의 수가 된다.

가져갈 수 있는 폰켓몬 개수 N/2 보다 중복 제거 벡터 nums의 크기가 더 크면 , 어차피 가져갈 수 있는 폰켓몬 개수는 N/2개 이므로 answer = N/2가 된다.

그리고 N/2 보다 작으면, 중복 제거 벡터 nums의 크기가 된다.

#include <vector>
#include <algorithm>

using namespace std;

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