[프로그래머스 | python3] 폰켓몬

코딩테스트 연습 - 폰켓몬

오늘의 교훈: 최대한 간단하게 생각하자! 

 

1. 첫번째 시도:

폰켓몬의 combinations를 만들어서 각 조합의 unique value를 세어 리스트로 만들어 준 뒤, max값을 추출하는 방식을 시도해보았다. 조합을 만들기 위해 itertools패키지의 combinations 함수를 사용했다. 

from itertools import combinations
def solution(nums):
    iterNum= int(len(nums)/2)
    lst= list(combinations(nums,iterNum))
    for i in range(len(lst)): lst[i]= len(set(lst[i]))
    return max(lst)

-> 시간초과

 

시간초과가 떴다. for문이 시간을 많이 잡아먹는 것이 원인이라고 생각하였다. 

 

 

2. 두번째시도: 

이번에는 lambda함수를 사용하여 코드를 조금만 변경한 후 다시 돌려보았다. 

from itertools import combinations
def solution(nums):
    iterNum= int(len(nums)/2)
    lst= list(combinations(nums,iterNum))
    return max(list(map(lambda x: len(set(x)), lst)))

-> 시간초과

 

마찬가지로 시간초과이다. 심지어 실행이 더 느려졌다. for문의 대체재로 lambda함수는 적합하지 않다. for문의 실행시간을 줄이기 위해선 list comprehension을 사용하는 방법 등이 있지만 이 문제에서 원하는 것은 그것이 아니다. 이 문제의 힌트는 

 

가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.

여기 이 제한사항에 있다. 어차피 어떤 조합이 있던 간에 최댓값 하나만 반환하면 되기 때문에 가능한 모든 조합을 생성해줄 필요가 없다. 즉, 위의 코드에서 조합을 구하는 코드를 모두 빼고 최댓값만을 구하기 위한 코드로 다시 작성하였다. 

 

 

3. 세번째시도:

우선 배열에서 폰켓몬의 타입 수를 set과 len함수로 구하고, 조합의 길이를 구해준다. 그리고 이 두 수의 최솟값이 폰켓몬 타입의 최대값이 된다.

만일 폰켓몬의 타입이 3가지이고 조합의 길이가 2면 어차피 폰켓몬의 타입은 최대로 2가지 밖에 들어가지 못하기 때문에 최댓값은 2이다.  반면 폰켓몬의 타입이 4가지이고 조합의 길이가 6이면 조합에 모든 폰켓몬 타입이 들어간다해도 최대가 4가지 이기 때문에 최댓값은 4이다. 즉 폰켓몬의 타입과 조합의 길이 중 최솟값이 바로 폰켓몬의 최대값이 되는 것이다. 

def solution(nums):
    typeNum= len(set(nums))
    combNum= int(len(nums))/2
    return int(min(typeNum, combNum))