폰켓몬

 

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

프로그래머스

문제풀이

처음엔 문제에서 n/2 마리의 폰켓몬을 가져가도 된다고 했기에 예시처럼 n/2마리로 만들 수 있는 모든 조합의 경우를 찾아낸다음 조합에서 중복되는 요소를 제거했을때 최대 길이를 정답으로 반환 하려 했었다.  

다만 제한사항 조건으로 위에 알고리즘을 사용해 풀게되면 O(2^N)의 시간 복잡도를 가지게 되어버린다

 

문제의 요지는 폰켓몬 종류 개수의 최댓값 이므로 주어진 입력에서 중복 제거를 한 값과 중복되지 않았을때 가져갈 수 있는 최대 종류 개수인 n/2 중에 최소값을 반환 하면 된다.

def solution(nums):
    t_set = set(nums)  # 중복 번호 제거
    # 중복 번호를 제거한 배열의 길이, 기존 배열 길이의 절반 값중 최소 값이 정답
    answer = min(len(t_set), len(nums) // 2)

    return answer