[프로그래머스] 폰켓몬

문제 설명

n(짝수)개의 포켓몬 중 n/2개만 잡아갈 수 있습니다.
포켓몬의 종류를 가장 다양화 해서 n/2개를 잡았을 때의 포켓몬 종류는 몇가지인지 구하세요.

아이디어

삽질

일단 조합 문제라고 접근을 해버려서 각 조합 certificate를 만들어서 종류를 세줬었다. 시간초과가 났다. (닭 잡는 일에 소 잡는 칼을 써버리신 라클님.....)

사실 단순한 문제라는 걸 뒤늦게 깨달음

종류를 다양화한 경우들의 조합 구성을 하나하나 알려달라는 게 아니고
그냥 종류를 최대로 다양화했을 때 몇 종류 가져갈 수 있냐는 문제다.
그리고 그건 그냥 산술적으로 자연에 있는 포켓몬의 종류를 구하고
n/2로 마스킹해주면 되는 문제다;;

포켓몬 종류 구하는 거는 포켓몬 배열을 돌면서 도감 배열에 수집 여부를 저장하여 있는 포켓몬은 무시해가며 구할 수 있었다.

새로이 알게 된것

배열을 선언할 때 초기화 값이 없어도 기본적으로 쓰레기 값 없이 0으로 초기화된다고 알고 있었다.
근데 그렇게 하니까 틀리는 테케가 몇개 있었다.

bool tab[200001]={false}; // 0으로 전체 초기화
bool tab[200001];// 쓰레기값 종종 있음

여담

나는 이게 마스킹 할 때 min함수를 써서 그런가 했는데 그건 문제가 아니었다.

코드

#include <vector>
#include<math.h>
using namespace std;

int solution(vector<int> nums)
{
    int answer = 0;
    //서로 다른 종류가 얼마나 있는지를 검사
    //1/2안에서 가져갈 수 있음
    bool tab[200001]={false};
    for(int i = 0;i<nums.size();i++){
        if(tab[nums[i]]==false){
            answer++;
            tab[nums[i]]=true;
        }
    }
    int n= nums.size();
    answer= min(answer,n/2);
    return answer;
}