폰켓몬

(중간 예시는 짤랐습니다)

접근 방식

1️⃣ 첫번째 알고리즘 (시간초과로 30점❌)

1. 주어진 리스트에서 조합 구하기
2. 각 조합 Counter 구해서 key 개수 저장
3. 가장 큰 key 개수 반환

이렇게 하니 아무래도 조합 계산 시 O(n!) 시간복잡도 때문인지 70점은 시간초과로 날라가길래 다른 방식으로 접근했다.

2️⃣ 두번째 알고리즘 (성공💯)

📌 어차피 문제에서 주목하는 건 종류이기 때문에 종류의 개수를 최대로 만드는 데 집중하면 된다

1. 주어진 list를 set으로 변환
2. set 개수와 n/2의 개수를 비교한다
   • set 개수 >= n/2의 개수
     : n/2의 개수
   • set 개수 < n/2의 개수
     : set 개수

👉 결론적으로 두번째 방법이 훨씬 좋은 게, 첫번째 방식은 combinations랑 Counter등 가져다 쓸 게 많았는데 두번째는 고려할 게 확 줄어든다! (파이썬 알못인 나에게 good😇)
시간복잡도는 말할 것도 없고

최종 코드

def solution(nums):
    nums_set = set(nums)
    
    if len(nums_set)>=(len(nums)//2):
        return (len(nums)//2)
    else:
        return len(nums_set)