[Programmers] #1845 - 폰켓몬 [Java][C++][Python]

문제 링크

---

1. 아이디어

총 N마리의 폰켓몬 중 절반(N / 2마리)을 선택할 때, 가능한 한 많은 종류를 가져가려면 서로 다른 종류의 수와 선택 가능한 마리 수 중 작은 쪽을 고르면 된다. 서로 다른 종류의 수보다 더 많이 골라봐야 어차피 중복이 생기고, 선택 가능한 마리 수보다 많이 가져갈 수도 없기 때문이다. 따라서 해시 집합에 모든 도감 번호를 담아 서로 다른 종류의 수를 구하고, N / 2와 비교해 작은 값을 반환해줬다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N)$	$O(N)$

($N$ = nums의 길이)

---

3. 코드

풀이 [Java][C++][Python]

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) {
            set.add(x);
        }

        return Math.min(set.size(), nums.length / 2);
    }
}

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

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

def solution(nums):
    return min(len(set(nums)), len(nums) // 2)

---