[프로그래머스] 폰켓몬

문제

연구실에 총 N 마리 중 N / 2 가져가도 됨
- 종류에 따라 번호 붙임
- 최대한 많은 종류를 갖길 원함

배열
종류 번호 : nums

총 길이 N : 1 이상 1만 이하 자연수, 짝수
종류 번호 : 1 이상 20만 이하 자연수 

@ 폰켓몬 종류 최댓값

생각

경우의 수로 나눌까?
1) 중복 다 제거 => N과 동일 (i.e. 중복 x) => N/2
2) 중복 다 제거 => 절반 값과 같거나 이상 => N/2
3) 중복 다 제거 => 절반 이하의 값 => 나머지는 이미 set에 있는 번호이므로 번호 종류의 최댓값은 set에서 고르는 것과 동일

도출

set 사용
set에서 N/2만큼 뽑으면 됨

 

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

int solution(vector<int> nums)
{
    int answer = 0;
    set<int> s (nums.begin(), nums.end());        
    return (s.size() >= nums.size() / 2) ? nums.size() / 2 : s.size();
}

 

아까 queue 문제를 풀다가, 결국 vector 사용이 훨씬 효율적이었던 걸 인지하였더니

hash문제인데 set으로 풀어서 간단히 해결했다.