[프로그래머스] 폰켓몬 c++

문제 설명

 

제한 사항

• nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.
• nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.
• 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.
• 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.

입출력 예

nums	result
[3,1,2,3]	2
[3,3,3,2,2,4]	3
[3,3,3,2,2,2]	2

 

문제 풀이

 

N마리의 폰켓몬 중 N/2를 가질 수 있다.

중복을 허용하지 않는 map을 사용해서 폰켓몬의 종류를 카운트한다.

map의 크기가 폰켓몬 종류 개수가 된다.

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

int solution(vector<int> nums)
{
    int answer = 0;
    
    map<int, int> H;
    for(auto &it : nums){
        H[it] += 1;
    }
    
    if(H.size()> (nums.size()/2)){
         answer = int(nums.size()) / 2;
    }   
    else{
         answer = H.size();
    }   
    
    return answer;
}

 

다른 풀이

 

set도 중복을 허용하지 않는 자료구조이다.

set은 오름차순 정렬되어 원소가 삽입 되고, unordered_set은 정렬되지 않고 원소가 삽입된 순서로 원소들이 저장된다.

 

set변수에 nums 벡터에 들어 있는 원소들로 초기화하여 생성한다.

int solution(vector<int> nums)
{
	unordered_set<int> s(nums.begin(), nums.end());
    return min(nums.size() / 2, s.size());
}