Programmers 1845 폰켓몬 (해시)

문제

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

$N$마리의 폰켓몬 중 $N/2$마리를 선택할 때, 선택할 수 있는 가장 다양한 폰켓몬 종류의 수를 구하는 문제입니다.

• nums 배열의 길이 $N$: $2 \le N \le 10,000$
• 폰켓몬 종류 번호: $1 \le \text{ID} \le 200,000$

복잡도 분석

• time complexity : $O(N)$
  • 배열 nums를 한 번 순회하며 해시 자료구조(Map/Set)에 삽입하므로 $O(N)$이 소요됩니다.
• space complexity : $O(N)$
  • 최악의 경우 모든 폰켓몬의 종류가 다를 때, 해시 자료구조에 $N$개의 원소가 저장됩니다.

접근법

핵심은 ‘욕심쟁이 알고리즘(Greedy)’의 관점에서 접근하는 것입니다. 우리가 가질 수 있는 최대 종류는 다음 두 값 중 작은 값에 의해 결정됩니다.

1. 물리적 한계: 우리가 뽑을 수 있는 최대 마릿수 ($N/2$)
2. 자원적 한계: 배열에 존재하는 고유한 폰켓몬 종류의 수

풀이

#include <vector>
#include <unordered_map>

using namespace std;

int solution(vector<int> nums) {
    int answer = 0;
    unordered_map<int, int> m;
    
    for(const auto& e : nums) {
        m[e]++;
    }

    // 종류의 수가 가질 수 있는 한도(size/2)를 넘으면 한도만큼, 
    // 아니라면 종류의 수만큼 반환
    if(m.size() > nums.size() / 2) {
        answer = nums.size() / 2;
    } else {
        answer = m.size();
    }
    
    return answer;
}

[개선된 코드 예시]

#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

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