[Python : 프로그래머스] 폰켓몬

문제

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

풀이

nums	result
[3,1,2,3]	2
[3,3,3,2,2,4]	3
[3,3,3,2,2,2]	2

우선 곧장 모든 조합을 구하는 것은 굉장히 무거우므로 배제한다.
안봐도 시간초과가 수두룩 하게 뜰 것이다.

“nums를 바로 중복배제 시킨 다음 모든 조합을 구해보자!”
라는 생각으로 접근해봤던 코드.

from itertools import combinations
def solution(nums):
    num = list(set(combinations(nums, len(nums)//2)))
    answer = 0
    for n in num :
        if answer < len(set(n)) : answer = len(set(n))
    return answer

시간초과가 우수수수수 쏟아졌다.
set을 통해 중복배제 시켰는데도 무겁다…

불필요하게 생성되는 조합이 없는지 고려해본다.
예제 3개 중 3번의 조합이 바로 그런 경우였다.

[3,3,3,2,2,2]

이 경우 조합을 구해보지 않아도 답이 2라는걸 알 수 있다.
아하, 처음 중복배제를 시켜봤을 때 이미 nums의 절반 보다 작으면 바로 답을 반환하자!

from itertools import combinations
def solution(nums):
    setnums = set(nums)
    if len(nums)//2 > len(setnums) : # 중복배제 길이가 이미 더 짧다면 종료
        return len(setnums)

    num = list(combinations(setnums, len(nums)//2))

    result = 0
    for n in num :
        if len(set(n)) > result :
            result = len(set(n))
    return result

이렇게 처리를 해줬음에도 시간초과가 계속 나왔다.
중복배제 후 반환시키는 라인을 멍하니 보다가 문뜩 머리에 스친 생각이…

어… 가져가라는 nums의 절반보다 중복배제가 더 작으면
어차피 최대종류는 중복배제고…
중복배제가 가져가라는 nums의 절반보다 크면
답이 nums의 절반인거 아닌가?

그대로 코드로 옮기다보니, 조합을 구할 필요도 없어졌다. 코드를 정리해봤다.

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

응 맞다. 조합을 구할 필요 자체가 없었다.
조합을 구해야하는 것처럼 지문이 적혀있었지만,
함정에 빠지지 않는다면 조합과는 관계없이 바로 답을 작성할 수 있는 문제였다.

채점 버튼 누르고 성공으로 도배되는 채점화면을 보면서
내가 문제의 본질을 파악하기보다 지문에 얼마나 신경을 쓰고있는가 깨달으면서
허탈하게 웃음이 나오는 문제였다.