[Python] 폰켓몬 - 해시

풀이

from itertools import combinations

def solution(nums):
    answer = 0

    num_len=len(set(nums)) #중복 없앤 애들 = 종류 개수 최대값
    res=len(nums)//2 #최대로 나올 수 있는 경우의 수
    if res < num_len:
        answer=res
    else:
        answer=num_len
    
    return answer

Git - 소스코드
더 간결하게

from itertools import combinations

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

결과

해석

해시 즉 요소의 중복이 불가능한 내장모듈 collection 자료형 Set을 사용했다.
처음 접근은 잘 했지만, 문제를 어떻게 풀어나가야 할지 모르겠어서 코드를 참고하여 해석한 결과 직관적으로 작성해야하는 것을 알았다.
처음에는 아래와 같은 코드로 참고한 코드와 같이 for문을 돌려 해결하고자 했다.

from itertools import combinations

def solution(nums):
    answer = 0

    result=[]
    
    for i in combinations(nums, int(len(nums)/2)):
        result.append(len(set(i)))
        
    answer=max(result)
    
    return answer

하지만 시간 초과 문제가 발생했다.
for문으로 인해 효율이 떨어진 것이다.

주석에서 쓴 것과 같이 중복을 없애면 최대로 나올 수 있는 폰켓몬 종류가 된다. 하지만 n/2마리까지만 가져갈 수 있기 때문에 중복없앤 뒤 나오는 최댓값이 n/2보다 크다면 n/2의 값이 나오게 되고, 아니라면, 중복 없앤 뒤 나오는 최댓값이 반환된다!