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

문제 링크

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

 

문제 설명

1. N/2마리의 폰켓몬을 선택하는 방법 중
2. 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아
3. 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

 

문제 입출력 예)

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

 

문제 풀이

Hash Table을 사용해서 문제에 접근했다.

포켓몬의 종류와 수를 각각의 map<int,int>에 넣는다.

최대로 가질 수 있는 포켓몬의 수는 N/2이다.

N/2 > map.size()가 성립할 경우 map.size()의 종류를 고를 수 있고

N/2 <= map.size()가 성립할 경우 N/2개의 종류를 고를 수 있다.

 

#include <vector>
#include <map>
#include <iostream>

using namespace std;


int solution(vector<int> nums)
{
    map<int, int> pok;
    for(int i=0; i<nums.size(); i++){
        pok[nums[i]]++;
    }
    
    return nums.size()/2 > pok.size()?pok.size():nums.size()/2;
}

 

 

• Hash map 문제가 재밌어졌다. ㅎㅋ