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

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

프로그래머스

풀이

N/2 마리의 포켓몬을 가져갈 때, 서로 다른 종으로 최대 몇종이 포함될 수 있는지 구하는 문제이다.

따라서,

1. 해시를 사용해 nums에서 중복을 제거해서 현재 포켓몬 종 수를 알아낸다.

2. 뽑아야 하는 포켓몬 수가 현재 포켓몬 종 수보다 작다면, 이 때 모든 포켓몬은 다른 종으로 뽑을 수 있다. 따라서 answer = 뽑아야 하는 포켓몬 수

3. 포켓몬 종 수가 뽑아야 하는 포켓몬 보다 작다면, 서로 다르게 뽑을 수 있는 최대는 현재 포켓몬 종 수이다. 따라서 answer= 현재 포켓몬 종 수

즉, 둘 중 최소값을 리턴하면 된다.

리뷰

아래는 map을 사용해 구현한 형태이다. 쉬운 문제였지만 set을 사용한 훨씬 간결한 풀이가 있어서 기록했다.

#include <vector>
#include <unordered_map>

using namespace std;

int solution(vector<int> nums)
{
    int answer = 0;
    unordered_map<int, int> hash;
    int spieces=0;
    for (int i=0; i<nums.size(); i++) {
        if (!hash[nums[i]]) spieces++;
        hash[nums[i]]=1;
    }
    
    int choiceNum = nums.size()/2;
    answer = min(spieces, choiceNum);
    return answer;
}

 

간결한 풀이

#include <bits/stdc++.h>
using namespace std;

int solution(vector<int> nums) {
    unordered_set<int> s(nums.begin(), nums.end());

    return min(nums.size() / 2, s.size());
}