Level 1 폰켓몬

첫 번째 풀이

시간 복잡도: O(n lgn)

1#include <bits/stdc++.h>
2using namespace std;
3
4int solution(vector<int> nums)
5{
6  int answer = 0;
7  sort(nums.begin(), nums.end());
8  int choose = (nums.size()) >> 1;
9  int types = 1;
10
11  for(int i=1; i<nums.size(); ++i) {
12    if(nums[i-1] != nums[i])
13      ++types;
14  }
15  return (types < choose) ? types : choose;
16}

O(nlgn)으로 구현되어 있는 sort() 함수를 사용하여 폰켓몬을 오름순으로 정렬한다. 그 다음, 폰켓몬의 종류(types)와 데려갈 N/2의 폰켓몬(choose)을/를 계산하고 둘 중 작은 값을 반환한다.

두 번째 풀이

시간 복잡도: O(n lgn)

1#include <bits/stdc++.h>
2using namespace std;
3
4int solution(vector<int> nums)
5{
6    int answer = 0;
7    set<int> s;
8    for(int p : nums) s.insert(p);
9    
10    return min(s.size(), nums.size()/2);
11}

set은 중복되는 값을 허용하지 않기 때문에 폰켓몬의 종류를 따로 계산하지 않아도된다. set에 최종 데이터가 폰켓몬의 총 종류이기 때문에 마지막에 set의 크기와 N/2를 비교해서 더 작은 값을 반환하면 된다.