[프로그래머스] 폰켓몬

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

코딩테스트 연습 - 폰켓몬

---

 

-풀이-

해당 번호의 폰켓몬이 나왔는지 확인 할 수 있는 bool check[200001]을 선언한다. check[i]=true이면 i번 폰켓몬을 종류의 수에 포함시켰다는 것이고, false이면 i번 폰켓몬을 종류의 수에 포함되지 않았다는 것이다.

따라서 nums배열을 돌며, 해당 폰켓몬이 종류의 수에 포함되지 않았다면, 종류의 수를 1 증가시킨 뒤, 해당 check[i]를 true로 설정해준다.

 

이렇게 nums배열에 총 몇종류가 있는지 확인을 한 뒤, 종류의 개수와 N/2를 비교하여, 더 작은 쪽이 가장 많은 종류의 폰켓몬을 선택하는것이 되는것이다.

 

-시간복잡도-

nums의 배열의 길이를 N이라고 한다면, O(N)시간이 된다.

 

-코드-

 

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

bool check[200001]={0};

int solution(vector<int> nums)
{
    int answer = 0;
    int n=nums.size();
    int race=0;
    //종류의 수를 세어주는 for문
    for(int i=0;i<n;i++){
        int now=nums[i];
        if(!check[now]){
            check[now]=true;
            race++;
        }
    }
    //종류의 수와 n/2를 비교하여 더 작은쪽이 최댓값
    answer=min(race,n/2);
    return answer;
}