연습문제 폰켓몬

프로그래머스

폰켓몬

• 총 N마리의 폰켓몬 중 N//2마리를 고르는 문제
• 골랐을 때 겹치지 않는 폰켓몬의 수를 반환
• 순열 문제로 생각할 수 있지만
• 순열로 해결하게 되면 시간 복잡도가 매우 커질 수 있다.
• 리스트에서 겹치는 원소를 제거하는 방향으로

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

set 을 이용하여 list 내부의 겹치는 원소를 제거해주었다.

target = N(list의 길이) // 2 인데 set으로 중복 원소를 제거해주고 set의 길이가 target 보다 작다면 반드시 중복해서 원소를 골라야 하므로, 겹치지 않는 원소의 수는

len(set(nums))가 된다. set의 길이가 target 보다 작지 않다면 반드시 target 수만큼 겹치지 않는 폰켓몬을 고를 수 있다.

Programmers