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

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

프로그래머스

 

N마리의 폰켓몬이 주어지며 각 폰켓몬은 고유 번호를 가진다.

 

[1, 3, 4, 1] 의 경우는 아래와 같다. 

1: 2마리

3: 1마리

4: 1마리

 

나는 N/2마리의 폰켓몬을 데려가길 원하고, 가장 많은 종류의 폰켓몬을 데려가려면 어떻게 해야 할까?

 

풀이 방법

Hashmap을 사용했다.

정렬의 필요가 없고 범위가 크다.

• 폰켓몬 종류번호 1 ~ 200,000
• 폰켓몬 수 1 ~ 10000

20만 범위의 배열을 사용할 수도 있지만 for문을 돌리는데 시간이 오래 걸린다.

그렇다면, 각 폰켓몬의 번호는 고유하므로 HashMap으로 <폰켓몬 고유번호, 특정 고유번호의 폰켓몬 수>를 저장한다.

그리고 HashMap의 사이즈를 확인하여 총 몇마리의 폰켓몬이 존재하는지 확인하면 된다. 

풀이 코드

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

unordered_map<int,int> ponketmon;
int solution(vector<int> nums){
    int answer = 0;
  
    for(int i : nums)ponketmon[i]++;
    int max_num = nums.size()/2;
    
    if(ponketmon.size() >= max_num) answer = max_num;
    else answer = ponketmon.size();
    
    return answer;
}