[문제]
https://school.programmers.co.kr/learn/courses/30/lessons/1845
N마리의 폰켓몬 중 N/2마리를 가져가려 한다. 폰켓몬은 종류에 따라 번호를 붙여 구분하기 때문에 같은 종류의 폰켓몬은 같은 번호를 가지고 있다.
N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 수를 return 하도록 solution 함수를 완성하는 문제이다.
[사용 알고리즘]
해시
[풀이 핵심]
- 이 문제는 set을 사용하면 정말 쉽게 해결할 수 있다. set이란말 쉽게 해결할 수 있다. set이란 고유한 값을 특정한 순서에 따라 저장하는 컨테이너이다. 고유한 값이라는 것은 중복을 허용하지 않는다는 것인데, 이 특징을 이용해서 문제를 풀면 쉽게 해결할 수 있다.
- 이 문제의 핵심은 같은 종류의 폰켓몬이 많아도 의미없다는 것이다. 따라서 set을 통해 중복되는 폰켓몬을 걸러주면, set의 size가 폰켓몬의 종류수가 된다.
- 폰켓몬의 종류수가 무조건 정답은 아니다. 왜냐하면 N/2마리의 폰켓몬을 가져갈 것이기 때문이다. 종류가 아무리 많아도 N/2마리 밖에 못 가져가므로 min(총 폰켓몬 수의 절반, 폰켓몬의 종류 수)가 정답이 된다.
[코드]
#include <vector>
#include <set>
using namespace std;
int solution(vector<int> nums)
{
int answer = 0;
set<int> s;
for(int i=0;i<nums.size();i++){
s.insert(nums[i]);
}
answer = min(nums.size()/2,s.size());
return answer;
}
