프로그래머스 폰켓몬 문제

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

N개의 폰켓몬 중에서 N/2개의 폰켓몬을 가져간다고 했을 때, 가져갈 수 있는 폰켓몬의 종류의 갯수를 구하는 문제였다.

nums = [3,1,2,3]  답 = 2
nums1 =  [3,3,3,2,2,4] 답 =3
nums2 = [3,3,3,2,2,2] 답  =2

 

코딩을 배우고 있는 입장에서 문제를 보면 천천히 문제를 간단하게 요약하기 위해서 적어보다가 해법이 대충 보였다.

 

리스트의 종류와 길이의 절반을 비교해서 출력하는 방법

 

그래서 머릿 속에서 생각한대로 포문을 돌려서 작성해버렸다.

 

def solution(nums):
    answer = 0
    for i in range(1, max(nums)+1):
        if i in nums:
            answer += 1
    if answer >= len(nums)/2:
        answer = len(nums)/2
    return int(answer)

그런데 문제는 N은 10,000이하의 자연수고

 

폰켓몬의 종류는 200,000까지 있다는 것

 

즉..포문을 돌려버리면 시간이 오래걸리고 효율적이지 못하다는 문제가 발생했다.

 

그래서 어떻게 시간을 줄일 수 있을 지에 대해 깊은 고민에 빠져버렸다.

 

리스트에 서로 다른 것만 어떻게 남기지...하다가 생각난 것이 set

 

def solution(nums):
    answer = 0
    nums2 = set(nums)
    if len(nums2) >= len(nums)/2:
        answer = len(nums)/2
    else:
        answer = len(nums2)
    return int(answer)

기존 코드에서 약간만 수정해서 제출하였더니 성공하였다.

 

그러고 다른 사람의 풀이도 봤는데

 

더 간단한 방법이 있었다. 맙소사

 

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

비슷한 내용이긴 한데 훨씬 심플한 느낌?

 

그래도 결이 비슷하니까 만족~